BOJ 5938 - Daisy Chains in the Field

문제

N개의 들판과 M개의 경로가 주어질 때, 1번 들판에서 도달할 수 없는 들판을 모두 찾아라.

입력

들판 수 N과 경로 수 M, 이후 M개의 양방향 경로가 주어진다.

출력

1번에서 도달할 수 없는 들판 번호를 한 줄씩 출력한다. 모두 도달 가능하면 0을 출력한다.

예제

입력	출력
`4 2` `1 2` `3 4`	`3` `4`

풀이

1번 노드에서 DFS를 수행하여 방문 가능한 노드를 표시하고, 미방문 노드를 출력한다.

양방향 인접 리스트로 그래프를 구성한다
1번에서 DFS를 시작하여 도달 가능한 모든 노드를 방문 처리한다
방문한 노드 수가 N이면 0을 출력한다
그렇지 않으면 미방문 노드 번호를 순서대로 출력한다

핵심 아이디어: 연결 요소 판별 문제로, 1번과 같은 연결 요소에 속하지 않는 노드가 답이다.

코드

#include <iostream>
#include <vector>
using namespace std;
 
int n, m, v[251], cnt;
vector<int> adj[251];
 
void dfs(int cur)
{
  v[cur] = 1;
  cnt++;
  for (int i = 0; i < adj[cur].size(); i++)
  {
    int nxt = adj[cur][i];
    if (!v[nxt])
      dfs(nxt);
  }
}
 
int main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
 
  cin >> n >> m;
  while (m--)
  {
    int u, v;
    cin >> u >> v;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
 
  dfs(1);
 
  if (cnt == n)
    cout << 0 << '\n';
  for (int i = 1; i <= n; i++)
  {
    if (!v[i])
      cout << i << '\n';
  }
  return 0;
}

복잡도

시간: O(V + E)
공간: O(V + E)

문제