BOJ 3295. 단방향 링크 네트워크

https://www.acmicpc.net/problem/3295

solved.ac: Platinum II (2024.09.10)

관찰과 아이디어를 요구하는 문제입니다.

 

먼저 분해의 가치는 곧 간선의 개수를 의미하게 된다는 점을 파악할 수 있어야 합니다.

또한, 각 노드마다 진입 차수와 진출 차수는 0, 또는 1이 되어야 합니다.

 

네, 신나게 이분 매칭을 때려주면 됩니다.

 

답안 코드

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

int n, m;
vector<int> node[1001];
int a[1001];
bool visited[1001];

bool dfs(int cur)
{
  for(auto nxt: node[cur])
    {
      if(visited[nxt]) continue;
      visited[nxt] = true;

      if(a[nxt] == -1 || dfs(a[nxt]))
      {
        a[nxt] = cur;
        return true;
      }
    }
  return false;
}

void solve()
{
  for(int i=0;i<n;i++) node[i].clear();
  memset(a,-1,sizeof(a));
  memset(visited,0,sizeof(visited));

  cin >> n >> m;
  while(m--)
    {
      int p, q;
      cin >> p >> q;
      node[p].push_back(q);
    }

  int res = 0;
  for(int i=0;i<n;i++)
    {
      memset(visited,0,sizeof(visited));
      if(dfs(i)) res++;
    }
  cout << res << '\n';
}

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);

  int T;
  cin >> T;
  while(T--) solve();
}