【强联通分量缩点】【Tarjan】bzoj1051 [HAOI2006]受欢迎的牛

浏览数：39 / 时间：2015年06月11日

就是看是否有一些点，从其他任何点出发都可到达

定理：有向无环图中唯一出度为0的点，一定可以由任何点出发均可达。

所以缩点，若出度为零的点（强联通分量）唯一，则答案为该强联通分量中点的度数。

若不唯一，答案为0，易证。

Code（懒得Tarjan，用了两次DFS）：

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<vector>
 4 using namespace std;
 5 vector<int>order;
 6 int v[100001],first[100001],next[100001],en;
 7 int a[50001],b[50001],scc[10001],num[10001],sum,chu[10001];
 8 bool vis[10001];
 9 int n,m;
10 inline void AddEdge(const int &U,const int &V){v[++en]=V;next[en]=first[U];first[U]=en;}
11 void Clear()
12 {
13     memset(v,0,sizeof(v));
14     memset(first,0,sizeof(first));
15     memset(next,0,sizeof(next));
16     en=0;
17 }
18 void dfs(int cur)
19 {
20     vis[cur]=true;
21     for(int i=first[cur];i;i=next[i])
22       if(!vis[v[i]])
23         dfs(v[i]);
24     order.push_back(cur);
25 }
26 void dfs2(int cur,int sum)
27 {
28     vis[cur]=true;
29     scc[cur]=sum;
30     num[sum]++;
31     for(int i=first[cur];i;i=next[i])
32       if(!vis[v[i]])
33         dfs2(v[i],sum);
34 }
35 void Scc()
36 {
37     for(int i=1;i<=n;i++)
38       if(!vis[i])
39         dfs(i);
40     memset(vis,false,sizeof(vis));Clear();
41     for(int i=1;i<=m;i++)AddEdge(b[i],a[i]);
42     int sz=order.size();
43     for(int i=sz-1;i>=0;i--)
44       if(!vis[order[i]])
45         dfs2(order[i],++sum);
46 }
47 int Exam()
48 {
49     int cnt=0,Record;
50     for(int i=1;i<=m;i++)
51       if(scc[a[i]]!=scc[b[i]])
52         chu[scc[a[i]]]++;
53     for(int i=1;i<=sum;i++)
54       if(!chu[i])
55         {
56           cnt++;
57           Record=i;
58           if(cnt==2)
59             return 0;
60         }
61     return num[Record];
62 }
63 int res;char C;
64 inline int Get()
65 {
66     res=0;C=‘*‘; 
67     while(C<‘0‘||C>‘9‘)C=getchar();
68     while(C>=‘0‘&&C<=‘9‘){res=res*10+(C-‘0‘);C=getchar();}
69     return res;
70 }
71 int main()
72 {
73     n=Get();m=Get();
74     for(int i=1;i<=m;i++){a[i]=Get();b[i]=Get();AddEdge(a[i],b[i]);}
75     Scc();printf("%d\n",Exam());
76     return 0;
77 }