텀 프로젝트

Problem link: https://www.acmicpc.net/problem/9466

트리-like한 그래프가 주어질 때, 사이클에 포함된 노드의 수를 세는 문제로 볼 수 있다.

DFS를 진행할 때, 노드 X를 방문하고 노드 Y를 방문하려는데 이미 Y가 방문된 상태라고 해보자.

만약, 노드 Y가 아직 DFS가 완료되지 않은 지점이라면 노드 Y~X사이의 모든 노드는 사이클에 속한다.

적당히 VISIT 배열과 VISTI COUNT, 그리고 방문 이력을 잘 저장해주고 있으면 어렵지 않게 풀 수 있다.

#include <iostream>
#include <vector>

using namespace std;

size_t N;
vector<size_t> TABLE;

size_t VISIT_CNT;
vector<size_t> HISTORY;
vector<size_t> VISITED;
vector<bool> FINISHED;
vector<bool> IN_CYCLE;

void Dfs(const size_t vtx)
{
  VISITED[vtx] = ++VISIT_CNT;
  HISTORY[VISIT_CNT] = vtx;

  if (VISITED[TABLE[vtx]] == 0)
  {
    Dfs(TABLE[vtx]);
  }
  else if (!FINISHED[TABLE[vtx]])
  {
    for (size_t it = VISITED[TABLE[vtx]]; it <= VISITED[vtx]; ++it)
    {
      IN_CYCLE[HISTORY[it]] = true;
    }
  }

  FINISHED[vtx] = true;
}

size_t Solve(void)
{
  VISIT_CNT = 0;

  for (size_t it = 0; it < N; ++it)
  {
    if (VISITED[it] == 0)
    {
      Dfs(it);
    }
  }

  size_t sole = 0;
  for (size_t it = 0; it < N; ++it)
  {
    if (!IN_CYCLE[it])
    {
      ++sole;
    }
  }

  return sole;
}

int main(void)
{
  // For faster IO
  ios_base::sync_with_stdio(false);
  cout.tie(nullptr);
  cin.tie(nullptr);

  size_t tc;
  cin >> tc;

  while (tc--)
  {
    // Read input
    cin >> N;

    TABLE.assign(N, 0);

    VISITED.assign(N, 0);
    HISTORY.assign(N + 1, 0);  /// First is sentinel

    FINISHED.assign(N, false);
    IN_CYCLE.assign(N, false);

    for (size_t it = 0; it < N; ++it)
    {
      cin >> TABLE[it];
      --TABLE[it];
    }

    // Solve
    cout << Solve() << '\n';
  }

  return 0;
}