首页 > 代码库 > 【强联通分量缩点】【Tarjan】bzoj1051 [HAOI2006]受欢迎的牛
【强联通分量缩点】【Tarjan】bzoj1051 [HAOI2006]受欢迎的牛
就是看是否有一些点，从其他任何点出发都可到达
定理：有向无环图中唯一出度为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 }
【强联通分量缩点】【Tarjan】bzoj1051 [HAOI2006]受欢迎的牛
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。