洛谷P2863 [USACO06JAN]The Cow Prom S （tarjan）

题目简述：一个有向图，求出这个图点数>1的强连通分量的个数。

那么就是tarjan求强联通分量的模板了。

记得要用一个数组标记节点是否在栈中。

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 const int N=1e5+10;

 4 int head[N],nxt[N<<1],to[N<<1],tot;

 5 int dfn[N],low[N],st[N],top,idx,cnt,sze[N];

 6 int n,m,a,b,ans;

 7 bool vis[N];//标记节点是否在栈中

 8

 9 void add(int u,int v){

10     nxt[++tot]=head[u];

11     head[u]=tot;

12     to[tot]=v;

13 }

14

15 void tarjan(int u){

16     low[u]=dfn[u]=++cnt;

17     st[++top]=u;

18     vis[u]=true;

19     for(int i=head[u];i;i=nxt[i]){

20         int v=to[i];

21         if(!dfn[v]){

22             tarjan(v);

23             low[u]=min(low[u],low[v]);

24         }

25         else if(vis[v]){

26             low[u]=min(low[u],dfn[v]);

27         }

28     }

29     if(low[u]==dfn[u]){

30         int v;

31         idx++;

32         do{

33             v=st[top--];

34             sze[idx]++;

35             vis[v]=false;

36         }while(v!=u);

37     }

38 }

39

40 int main(){

41     scanf("%d%d",&n,&m);

42     while(m--){

43         scanf("%d%d",&a,&b);

44         add(a,b);

45     }

46     for(int i=1;i<=n;i++){

47         if(!dfn[i]) tarjan(i);

48     }

49     int ans=0;

50     for(int i=1;i<=idx;i++){

51         if(sze[i]>1) ans++;

52     }

53     printf("%d\n",ans);

54 }

洛谷P2863 [USACO06JAN]The Cow Prom S （tarjan）的相关教程结束。