SCC(strongly connected component)

작성일 | In | views

강한 연결 요소

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
#include <bits/stdc++.h>
using namespace std;
const int sz=100001;
//sz : n+1로 설정.
int dfsn[sz],scc[sz],dfsnumber,sccnumber;
//graph : 처음 주어지는 그래프 / dag : SCC로 묶인 그래프 / group[i] : i번 scc 노드에 묶여있는 노드들.
vector<int> graph[sz],dag[sz],group[sz];
stack<int> s;
int indegree[sz];

//타잔 알고리즘 이용.(scc 결과의 역순이 위상정렬한 dag 의 결과와 같음.)
int SCC(int node)
{
    dfsn[node]=++dfsnumber;
    s.push(node);
    int topmost=dfsn[node];
    for(int to:graph[node])
        if(!dfsn[to]) topmost=min(topmost, SCC(to));
        else if(!scc[to]) topmost=min(topmost,dfsn[to]);

    if(topmost==dfsn[node])
    {
        ++sccnumber;
        while(true)
        {
            int t=s.top();
            s.pop();
            scc[t]=sccnumber;
            group[sccnumber].push_back(t);
            if(t==node) break;
        }
    }
    return topmost;
}

void init(int n)
{
    dfsnumber=0,sccnumber=0;
    for(int i=1;i<=n;i++)
        graph[i].clear(),dag[i].clear(),dfsn[i]=0,indegree[i]=0,scc[i]=0,group[i].clear();
}

int main(void)
{
    int tc;
    scanf("%d",&tc);
    while(tc--)
    {
        int n,m;
        scanf("%d %d", &n,&m);
        while(m--)
        {
            int x,y;
            scanf("%d %d",&x,&y);
            graph[x].push_back(y);
        }
        for(int i=1;i<=n;i++)
            if(!dfsn[i]) SCC(i);

        //이제 위상정렬이 가능해짐.
        for(int node=1;node<=n;node++)
            for(int to:graph[node])
                if(scc[node]!=scc[to])
                {
                    dag[scc[node]].push_back(scc[to]);
                    indegree[scc[to]]++;
                }

        int ans=0;
        for(int i=1;i<=sccnumber;i++)
            if (!indegree[i]) ans++;
        printf("%d\n",ans);
        init(n);
    }
    return 0;
}

시간복잡도

$O(V+E)$

V : 노드 수, E : 간선 수

관련문제

백준4196 : 도미노