GGAutomaton's Blog
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
//针对有向图
void dfs(int x) {
    f[x]=true;
    d[x]=low[x]=++Time;
    sta.push(x);instack[x]=true;
    for (int e=head[x];e!=0;e=next[e]) {
        if (!f[vet[e]]) {
            dfs(vet[e]);
            low[x]=min(low[x],low[vet[e]]);
        }
        else if (instack[vet[e]]) low[x]=min(low[x],d[vet[e]]);
    }
    if (low[x]==d[x]) {
        idnum++;
        while (sta.top()!=x) {
            instack[sta.top()]=false;
            idc[sta.top()]=idnum;
            sta.pop();
        }
        idc[x]=idnum;
        instack[x]=false;
        sta.pop();
    }
}
int main() {
    int n;
    cin >> n;
    while (!sta.empty()) sta.pop();
    
    for (int i=1;i<=n;i++)
        if (!f[i]) dfs(i);
    for (int i=1;i<=n;i++)
        for (int e=head[i];e!=0;e=next[e])//遍历每条边
            if (idc[i]!=idc[vet[e]]) ind[idc[vet[e]]]++;
    
    return 0;
}