[4196번] 도미노

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. SCC :: http://www.crocus.co.kr/950

이 문제는 SCC를 구성한 후, Indegree 즉 진입차수를 구하면 되는 문제이다.

도미노를 넘어뜨릴 때 어떻게 해도 다른 도미노에 의해 넘어가지 않는 도미노를 찾아야 하는데

이때 도미노들이 SCC를 이루었을 때 서로 다른 SCC에서 u->v로 가는 경로가 존재하는 u를 찾아야 한다.

만약 이렇게 도미노가 있었다고 보자.

위의 그리프는 1을 넘기면 3이 넘어가지만 2는 넘어가지 않는다. 3을 넘기면 1은 넘어가지만 2는 넘어가지 않는다.

그렇지만 2를 넘기면 3과 1이 넘어간다.

결국 2의 진입차수는 0이라는 의미이고 진입차수가 0인 값들을 모두 구하면 된다는 의미이다.

소스 코드 : 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108

#include <iostream> #include <cstdio> #include <algorithm> #include <stack> #include <vector> #include <memory.h>   using namespace std;   const int MAX = 101000;   vector<int> adj[MAX]; stack<int> s;   bool finish[MAX]; // SCC 분리가 완료된 정점 = true int dfsn[MAX]; // 각 노드 dfs 번호 int SCCnum[MAX]; // SCC의 인덱스 번호 int indegree[MAX]; int cnt; // dfs 번호 int SCCtotal; // SCC 총 개수   int dfs(int cur) {     dfsn[cur] = ++cnt;       s.push(cur);       int result = dfsn[cur];       int len = adj[cur].size();       for (int i = 0; i < len; i++)     {         int next = adj[cur][i];           if (!dfsn[next])             result = min(result, dfs(next));           else if (!finish[next])             result = min(result, dfsn[next]);     }       if (result == dfsn[cur])     {         while (1)         {             int t = s.top();             s.pop();             finish[t] = true;             SCCnum[t] = SCCtotal;               if (t == cur)                 break;         }           SCCtotal++;     }       return result; }   int main() {     int tc;     scanf("%d", &tc);     while (tc--)     {         int V, E;         scanf("%d %d", &V, &E);           for (int i = 0; i < MAX; i++)             adj[i].clear();           memset(finish, false, sizeof(finish));         memset(dfsn, 0, sizeof(dfsn));         memset(SCCnum, 0, sizeof(SCCnum));         memset(indegree, 0, sizeof(indegree));         cnt = 0;         SCCtotal = 0;           for (int i = 0; i < E; i++)         {             int from, to;             scanf("%d %d", &from, &to);             adj[from].push_back(to);         }           for (int i = 1; i <= V; i++)             if (!dfsn[i])                 dfs(i);           for (int i = 1; i <= V; i++)             for (int j : adj[i])                 if (SCCnum[i] != SCCnum[j])                     indegree[SCCnum[j]]++;           int cnt = 0;         for (int i = 0; i < SCCtotal; i++)             if (indegree[i] == 0)                 cnt++;           printf("%d\n",cnt);     }     return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus