OI

【模板】Tarjan

tarjan模板：

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<iostream>
#include<cstdio>
#include<stack>
#include<cstring>
using namespace std;
const int MAX=10005,MAXM=50005;
int dfn[MAX]={0},low[MAX]={0},indx=0;
stack<int> s;
bool vis[MAX]={0};

struct edge{
    int next,to;
};
edge g[MAXM];
int head[MAX]={0},nume=-1;

int color[MAX]={0},cnt[MAX]={0},sum=0;
int n,m;

void adde(int f,int t){
    g[++nume].next=head[f];
    g[nume].to=t;
    head[f]=nume;
}

void tarjan(int u){
    dfn[u]=++indx;
    low[u]=indx;
    vis[u]=1;
    s.push(u);
    
    for(int i=head[u];i!=-1;i=g[i].next){
        int v=g[i].to;
        if(dfn[v]==0){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(vis[v])
            low[u]=min(low[u],low[v]);
    }
    
    if(dfn[u]==low[u]){
        color[u]=++sum;
        vis[u]=0;
        while(s.top()!=u){
            color[s.top()]=sum;
            vis[s.top()]=0;
            s.pop();
        }
        s.pop();
    }
    
}

int main(){
    memset(head,-1,sizeof(head));
    scanf("%d%d",&n,&m);
    int x,y;
    for(int i=1;i<=m;i++){
        scanf("%d%d",&x,&y);
        adde(x,y);
    }
    
    for(int i=1;i<=n;i++)
        if(dfn[i]==0)tarjan(i);
    
    for(int i=1;i<=n;i++)
        cnt[color[i]]++;
    
    int ans=0;
    for(int i=1;i<=sum;i++)
        if(cnt[i]>1)ans++;
    
    printf("%d\n",ans);
    return 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
#include<iostream>
#include<cstdio>
#include<stack>
#include<cstring>
using namespace std;
const int MAX=10005,MAXM=50005;
int dfn[MAX]={0},low[MAX]={0},indx=0;
stack<int> s;
bool vis[MAX]={0};

struct edge{
    int next,to;
};
edge g[MAXM];
int head[MAX]={0},nume=-1;

int color[MAX]={0},cnt[MAX]={0},du[MAX],sum=0,tmp,ans;
int n,m;

void adde(int f,int t){
    g[++nume].next=head[f];
    g[nume].to=t;
    head[f]=nume;
}

void tarjan(int u){
    dfn[u]=++indx;
    low[u]=indx;
    vis[u]=1;
    s.push(u);
    
    for(int i=head[u];i!=-1;i=g[i].next){
        int v=g[i].to;
        if(dfn[v]==0){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(vis[v])
            low[u]=min(low[u],low[v]);
    }
    
    if(dfn[u]==low[u]){
        color[u]=++sum;
        vis[u]=0;
        while(s.top()!=u){
            color[s.top()]=sum;
            vis[s.top()]=0;
            s.pop();
        }
        s.pop();
    }
    
}

int main(){
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF){
        memset(vis,0,sizeof(du));
        memset(vis,0,sizeof(low));
        memset(dfn,0,sizeof(dfn));
        memset(vis,0,sizeof(vis));
        memset(vis,0,sizeof(cnt));
        memset(vis,0,sizeof(color));
        //memset(vis,0,sizeof(stack));
        while(!s.empty())s.pop();
        memset(head,-1,sizeof(head));
        nume=-1;
        int x,y;
        for(int i=1;i<=m;i++){
            scanf("%d%d",&x,&y);
            adde(x,y);
        }
        
        for(int i=1; i<=n; i++)
            if(dfn[i]==0)
                tarjan(i);
        
        for(int i=1; i<=n; i++){
            for(int j=head[i];j!=-1;j=g[j].next){
                int v=g[j].to;
                if(color[v]!=color[i])
                    du[color[i]]++;
            }
            cnt[color[i]]++;
        }
        
        for(int i=1; i<=sum; i++)
            if(du[i]==0){
                tmp++;
                ans=cnt[i];
            }
        
        if(tmp==0)printf("0\n");
        else if(tmp>1)printf("0\n");
        else printf("%d\n",ans);
    }
}