boj 4196 도미노

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

4196번: 도미노

SCC 그룹후 이것을 처리하는 방법에서 막히였다. 만일 이런 SCC 그룹이 존재할때 답은 2라는것은 직관적으로 알것이다.

하지만 어떻게 2라는걸 나타낼 것인가??? 답은 밑에

 

 

 

 

 

Group에 대한 위상정렬 indegree배열을 만들고 indegree가 0인 개수를 새주면 된다.

즉 group1, 3이 0이니깐 답은 2개. 놀랍다!!

 

 

 

 

 

 

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;
 
 
vector<int> edge[100001];
stack<int>s;
bool finish[100001];
int dfsn[100001];
int group[100001];
int indegree[100001];
int g_num;
int dcnt;
int v, e;
 
int SCC(int cur)
{
    dfsn[cur] = ++dcnt;
    s.push(cur);
    int result = dfsn[cur];
    for (int i = 0; i < edge[cur].size(); i++)
    {
        int next = edge[cur][i];
        if (dfsn[next] == 0)
            result = min(result, SCC(next));
        else if (finish[next] == false)
            result = min(result, dfsn[next]);
    }
 
    if (result == dfsn[cur])
    {
        g_num++;
        while (!s.empty())
        {
            int t = s.top();
            s.pop();
            group[t] = g_num;
            finish[t] = true;
            if (t == cur)
                break;
        }
    }
 
    return result;
}
 
void init()
{
    
    for (int i = 1; i <= v; i++)
    {
        edge[i].clear();
        dfsn[i] = 0;
        finish[i] = false;
        group[i] = 0;
        indegree[i] = 0;
    }
    dcnt = 0;
    g_num = 0;
}
 
int main()
{
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    int tc;
    cin >> tc;
 
    for (int z = 0; z < tc; z++)
    {
        
        int a,b;
        cin >> v >> e;
        init();
 
 
        for (int i = 0; i < e; i++)
        {
            cin >> a >> b;
            edge[a].push_back(b);
        }
 
        for (int i = 1; i <= v; i++)
        {
            if (dfsn[i] == 0)
                SCC(i);
        }
 
        for (int i = 1; i <= v; i++)
        {
            for (int j = 0; j < edge[i].size(); j++)
            {
                a = group[i]; b = group[edge[i][j]];
                if (a == b)
                    continue;
                indegree[b]++;
            }
        }
        int ans = 0;
        for (int i = 1; i <= g_num; i++)
        {
            if (indegree[i] == 0)
                ans++;
        }
        cout << ans << '\n';
        
    }
}