[백준 9466] 텀 프로젝트 (C#, C++) - soo:bak

문제 링크

9466번 - 텀 프로젝트

설명

N명의 학생이 각각 함께 팀을 하고 싶은 학생 한 명을 선택하는 상황에서, N ≤ 100,000이 주어질 때, 각 학생의 선택이 주어지고 팀은 자기 자신으로 돌아오는 사이클을 이루어야 한다는 조건 하에 어느 팀에도 속하지 못한 학생 수를 구하는 문제입니다.

각 학생이 단 한 명을 선택하므로 단방향 그래프가 형성되며, 팀이 되려면 사이클을 이루어야 합니다. 따라서 사이클에 속하지 않는 노드의 개수를 구하면 됩니다.

접근법

DFS를 활용하여 사이클을 찾고 사이클에 속한 학생 수를 계산합니다.

먼저 두 개의 상태 배열을 사용합니다. visited는 해당 노드의 DFS 진입 여부를, done은 해당 노드의 탐색 완료 여부를 나타냅니다.

다음으로 각 노드에서 DFS를 시작하여 다음 노드로 이동합니다. 이동한 노드가 visited이지만 done이 아니라면 사이클을 발견한 것이므로, 사이클에 속한 모든 노드를 카운트합니다.

이후 DFS가 완료되면 해당 노드를 done으로 표시합니다. 이렇게 하면 모든 노드를 한 번씩만 방문하여 사이클을 찾을 수 있습니다.

시간 복잡도는 O(N)입니다.

---

Code

C#

using System;

namespace Solution {
  class Program {
    static int n, matched;
    static int[] pick;
    static bool[] visited, done;

    static void Dfs(int cur) {
      visited[cur] = true;
      var nxt = pick[cur];
      if (!visited[nxt]) {
        Dfs(nxt);
      } else if (!done[nxt]) {
        for (var v = nxt; ; v = pick[v]) {
          matched++;
          if (v == cur)
            break;
        }
      }
      done[cur] = true;
    }

    static void Main(string[] args) {
      var tc = int.Parse(Console.ReadLine()!);
      while (tc-- > 0) {
        n = int.Parse(Console.ReadLine()!);
        pick = new int[n + 1];
        visited = new bool[n + 1];
        done = new bool[n + 1];
        matched = 0;

        var parts = Console.ReadLine()!.Split();
        for (var i = 1; i <= n; i++)
          pick[i] = int.Parse(parts[i - 1]);

        for (var i = 1; i <= n; i++)
          if (!visited[i])
            Dfs(i);

        Console.WriteLine(n - matched);
      }
    }
  }
}

C++

#include <bits/stdc++.h>
using namespace std;

typedef vector<int> vi;
typedef vector<bool> vb;

int n, matched;
vi pick;
vb visited, done;

void dfs(int cur) {
  visited[cur] = true;
  int nxt = pick[cur];
  if (!visited[nxt]) {
    dfs(nxt);
  } else if (!done[nxt]) {
    for (int v = nxt;; v = pick[v]) {
      matched++;
      if (v == cur)
        break;
    }
  }
  done[cur] = true;
}

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

  int tc; cin >> tc;
  while (tc--) {
    cin >> n;
    pick.assign(n + 1, 0);
    visited.assign(n + 1, false);
    done.assign(n + 1, false);
    matched = 0;

    for (int i = 1; i <= n; i++)
      cin >> pick[i];

    for (int i = 1; i <= n; i++)
      if (!visited[i])
        dfs(i);

    cout << n - matched << "\n";
  }

  return 0;
}