洛谷P2863 [USACO06JAN]牛的舞会The Cow Prom

Description

求图中大于1的强连通分量的个数

Input

第一行 n个顶点条边

2-2+m-1行每条有向边的起点终点

Output

个数

题解：tarjan缩点求强连通分量，最后统计一下大于一的强连通分量的个数。

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<algorithm>
 5 #define maxn 10005
 6 
 7 using namespace std;
 8 
 9 struct node
10 {
11     int ed,nxt;
12 };
13 node edge[maxn*5];
14 int n,m,first[maxn],css[maxn],cs;
15 bool vis[maxn];
16 int s[maxn],ans,top,cnt; 
17 int dfn[maxn],low[maxn],tim,size[maxn];
18 
19 inline void add_edge(int s,int e)
20 {
21     cnt++;
22     edge[cnt].ed=e;
23     edge[cnt].nxt=first[s];
24     first[s]=cnt;
25     return;
26 }
27 
28 inline void tarjan(int k)
29 {
30     dfn[k]=low[k]=++tim; s[++top]=k;
31     for(register int i=first[k];i;i=edge[i].nxt)
32     {
33         int e=edge[i].ed;
34         if(!dfn[e])
35         {
36             tarjan(e);
37             low[k]=min(low[k],low[e]);
38         }
39         else if(!css[e]) low[k]=min(low[k],low[e]);
40     }
41     if(low[k]==dfn[k])
42     {
43         cs++;
44         while(s[top]!=k)
45         {
46             css[s[top]]=cs; size[cs]++; top--;
47         }
48         css[s[top]]=cs; size[cs]++; top--;
49     }
50     return;
51 }
52 
53 int main()
54 {
55     scanf("%d%d",&n,&m);
56     for(register int i=1;i<=m;i++)
57     {
58         int s,e;
59         scanf("%d%d",&s,&e);
60         add_edge(s,e);
61     }
62     for(register int i=1;i<=n;i++)
63         if(!dfn[i]) tarjan(i);
64     for(register int i=1;i<=cs;i++)
65         if(size[i]>1) ans++;
66     printf("%d
",ans);
67     return 0;
68 }