[백준 9466] 텀 프로젝트

www.acmicpc.net/problem/9466

9466번: 텀 프로젝트

directed graph에서 cycle detection 응용문제이다.

사이클에 해당하지 않는 노드를 찾는 문제로 dfs를 사용하거나 indegree + 위상정렬을 사용한다.

 

1. dfs를 사용할 때

사이클이 있는지 확인할 때 지나간지 여부를 체크하는 배열 path와

확인이 끝났다는 표식인 done 배열 두 가지를 사용한다.

 

1부터 n까지 done이 아니라면 dfs에 들어가는데

dfs에 들어가서 방문 체크path를 한다. 그 다음 노드가 방문 체크되지 않았다면 dfs를 다시 시작한다.

만약 다음 노드가 이미 방문한 노드라면 사이클이 존재한다는 의미이다. 

이미 체크가 끝난 노드가 아니라면 사이클을 시작해서 사이클 내의 노드가 몇개인지 세준다.

 

중간이 path[j]이든 done[j]이든 상관없다.

#include <stdio.h>
#include <string.h>

using namespace std;

const int MAX = 100000 + 1;
int t, n, cnt;
int arr[MAX];
bool path[MAX];
bool done[MAX];

void DFS(int node)
{
  path[node] = true;

  int nextNode = arr[node];

  if (!path[nextNode])
  {
    DFS(nextNode);
  }
  else if (!done[nextNode])
  {
    for (int i = nextNode; i != node; i = arr[i])
    {
      cnt++;
    }
    cnt++;
  }
  done[node] = true;
}
int main(void)
{
  scanf("%d", &t);
  for (int i = 0; i < t; i++)
  {
    scanf("%d", &n);
    cnt = 0;
    memset(done, false, sizeof(bool) * (n + 1));
    memset(path, false, sizeof(bool) * (n + 1));
    for (int j = 1; j <= n; j++)
    {
      scanf("%d", &arr[j]);
    }

    for (int j = 1; j <= n; j++)
    {
      if (!path[j]) // if(!visited[j])
        DFS(j);
    }

    printf("%d\n", n - cnt);
  }

  return 0;
}

 

2. indegree와 위상정렬

사이클이 있다는 건 indegree와 outdegree가 모두 1이상이라는 의미이다.

따라서 indegree가 없는 친구들을 세줄 예정이다.

 

indegree를 전부 카운트한 다음에

 

dfs

이미 방문한 적 없거나 indegree= 0 이라면 카운트하고 해당 노드를 방문한다.

해당 노드와 연결된 노드의 indegree를 --하고 다시 그 노드가 indegree = 0 && not visited라면 dfs를 진행한다.

 

 

#include <stdio.h>
#include <algorithm>

using namespace std;

const int MAX = 100000 + 1;
int t, n, cnt;
int arr[MAX];
int visited[MAX];
int indegree[MAX];

void DFS(int node)
{
  visited[node] = 1;
  cnt++;
  int next = arr[node];
  indegree[next]--;
  if (visited[next] == 0 && indegree[next] == 0)
  {
    DFS(next);
  }
}
int main(void)
{
  scanf("%d", &t);
  for (int i = 0; i < t; i++)
  {
    scanf("%d", &n);
    cnt = 0;
    fill(visited, visited + n + 1, 0);
    fill(indegree, indegree + n + 1, 0);
    for (int j = 1; j <= n; j++)
    {
      scanf("%d", &arr[j]);
      indegree[arr[j]]++;
    }

    for (int j = 1; j <= n; j++)
    {
      if (visited[j] == 0 && indegree[j] == 0)
        DFS(j);
    }

    printf("%d\n", cnt);
  }

  return 0;
}