首页 > 代码库 > bzoj 1051 (强连通) 受欢迎的牛
bzoj 1051 (强连通) 受欢迎的牛
题目：这里
题意：
Description
每一头牛的愿望就是变成一头最受欢迎的牛。现在有N头牛，给你M对整数(A,B)，表示牛A认为牛B受欢迎。 这
种关系是具有传递性的，如果A认为B受欢迎，B认为C受欢迎，那么牛A也认为牛C受欢迎。你的任务是求出有多少头
牛被所有的牛认为是受欢迎的。
Input
第一行两个数N,M。 接下来M行，每行两个数A,B，意思是A认为B是受欢迎的（给出的信息有可能重复，即有可
能出现多个A,B）
Output
一个数，即有多少头牛被所有的牛认为是受欢迎的。
Sample Input
3 3
1 2
2 1
2 3
1 2
2 1
2 3
Sample Output
1
HINT
100%的数据N<=10000,M<=50000
我是看了强连通入门(讲的很清楚)：http://www.2cto.com/kf/201606/517227.html
Kosaraju算法第一次dfs1将所有的点按拓扑排序逆序存进栈，第二次dfs2(此时是逆着方向回去搜)将整个图分成若干个强连通分量，。
对于这个题，可以观察出最后受到所有牛的欢迎的牛必定是在其中一个强连通分量里面的，所以看哪个强连通分量是其余所有变量都能达到的，也就等同于缩点后的
新图里面哪个的出度为0，如果出度为0的分量只有一个，那么该分量其中点的个数就是答案，如果出度为0的分量个数超过一个，那么没有答案，输出为0.
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<algorithm> 5 #include<vector> 6 #include<map> 7 #include<cmath> 8 using namespace std; 9 10 const int M = 1e5 + 10;11 vector<int>q;12 int sccno[M],sum[M],du[M],scc_cnt;13 14 struct Edge{15 int to,next,from,odr;16 }edge[M*2];17 int head1[M],head2[M],cas;18 bool vis[M];19 20 void add(int u,int v)21 {22 edge[++cas].next=head1[u];23 edge[cas].odr=head2[v];24 edge[cas].to=v;edge[cas].from=u;25 head1[u]=cas;head2[v]=cas;26 }27 28 void dfs1(int u)29 {30 for (int i=head1[u] ; i ; i=edge[i].next){31 int v=edge[i].to;32 if (vis[v]) continue;33 vis[v]=true;34 dfs1(v);35 q.push_back(v);36 }37 }38 39 void dfs2(int u)40 {41 sccno[u]=scc_cnt;42 sum[scc_cnt]++;43 for (int i=head2[u] ; i ; i=edge[i].odr){44 int v=edge[i].from;45 if (sccno[v]) continue;46 dfs2(v);47 }48 }49 50 int main()51 {52 int n,m;53 scanf("%d%d",&n,&m);54 scc_cnt=0;cas=0;55 q.clear();56 while (m--){57 int x,y;58 scanf("%d%d",&x,&y);59 add(x,y);60 }61 memset(vis,false,sizeof(vis));62 memset(sum,0,sizeof(sum));63 memset(du,0,sizeof(du));64 for (int i=1 ; i<=n ; i++)65 if (vis[i]==false){66 vis[i]=true;dfs1(i);67 q.push_back(i);68 }69 70 for (int i=n-1 ; i>=0 ; i--){71 if (!sccno[q[i]]){72 scc_cnt++;73 // cout<<q[i]<<endl;74 dfs2(q[i]);75 }76 }77 78 for (int i=1 ; i<=cas ; i++){79 int x=sccno[edge[i].from],y=sccno[edge[i].to];80 if (x==y) continue;81 du[x]++;82 }83 int flag=-1,ans;84 for (int i=1 ; i<=scc_cnt ; i++)85 if (!du[i]) flag++,ans=sum[i];86 if (flag==0) printf("%d\n",ans);87 else puts("0");88 return 0;89 }
Tanjan算法链接也就讲的很清楚了
1 #include<cstdio> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<stack> 6 using namespace std; 7 8 const int M = 1e5 + 10; 9 int head[M],cas,scc_cnt,dfs_clock;10 int sccno[M],du[M],sum[M],lowlink[M],pre[M];11 stack<int>s;12 13 int min(int x,int y){return x<y?x:y;}14 15 struct Edge{16 int to,next,from;17 }edge[M*2];18 19 void add(int u,int v)20 {21 edge[++cas].next=head[u];22 edge[cas].to=v;edge[cas].from=u;23 head[u]=cas;24 }25 26 void dfs(int u)27 {28 pre[u]=lowlink[u]=++dfs_clock;29 s.push(u);30 for (int i=head[u] ; i ; i=edge[i].next){31 int v=edge[i].to;32 if (!pre[v]){33 dfs(v);34 lowlink[u]=min(lowlink[u],lowlink[v]);35 }36 else if (!sccno[v]){37 lowlink[u]=min(lowlink[u],pre[v]);38 }39 }40 if (lowlink[u]==pre[u]){41 scc_cnt++;42 for ( ; ; ){43 int x=s.top();s.pop();44 sccno[x]=scc_cnt;45 if (x==u) break;46 }47 }48 }49 50 int main()51 {52 int n,m;53 scanf("%d%d",&n,&m);54 cas=0,dfs_clock=0,scc_cnt=0;55 while (m--){56 int x,y;57 scanf("%d%d",&x,&y);58 add(x,y);59 }60 memset(pre,0,sizeof(pre));61 memset(lowlink,0,sizeof(lowlink));62 memset(du,0,sizeof(du));63 memset(sum,0,sizeof(sum));64 for (int i=1 ; i<=n ; i++)65 if (!pre[i]) dfs(i);66 for (int i=1 ; i<=n ; i++)67 sum[sccno[i]]++;68 for (int i=1 ; i<=cas ; i++){69 int u=sccno[edge[i].from],v=sccno[edge[i].to];70 if (u==v) continue;71 du[u]++;72 }73 int flag=0,ans;74 for (int i=1 ; i<=scc_cnt ; i++)75 if (!du[i]) flag++,ans=sum[i];76 if (flag==1) printf("%d\n",ans);77 else puts("0");78 return 0;79 }
bzoj 1051 (强连通) 受欢迎的牛
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。