bzoj 1051 (强连通) 受欢迎的牛
2024-08-31 18:41:26
题目:这里
题意:
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.
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<cmath>
using namespace std; const int M = 1e5 + ;
vector<int>q;
int sccno[M],sum[M],du[M],scc_cnt; struct Edge{
int to,next,from,odr;
}edge[M*];
int head1[M],head2[M],cas;
bool vis[M]; void add(int u,int v)
{
edge[++cas].next=head1[u];
edge[cas].odr=head2[v];
edge[cas].to=v;edge[cas].from=u;
head1[u]=cas;head2[v]=cas;
} void dfs1(int u)
{
for (int i=head1[u] ; i ; i=edge[i].next){
int v=edge[i].to;
if (vis[v]) continue;
vis[v]=true;
dfs1(v);
q.push_back(v);
}
} void dfs2(int u)
{
sccno[u]=scc_cnt;
sum[scc_cnt]++;
for (int i=head2[u] ; i ; i=edge[i].odr){
int v=edge[i].from;
if (sccno[v]) continue;
dfs2(v);
}
} int main()
{
int n,m;
scanf("%d%d",&n,&m);
scc_cnt=;cas=;
q.clear();
while (m--){
int x,y;
scanf("%d%d",&x,&y);
add(x,y);
}
memset(vis,false,sizeof(vis));
memset(sum,,sizeof(sum));
memset(du,,sizeof(du));
for (int i= ; i<=n ; i++)
if (vis[i]==false){
vis[i]=true;dfs1(i);
q.push_back(i);
} for (int i=n- ; i>= ; i--){
if (!sccno[q[i]]){
scc_cnt++;
// cout<<q[i]<<endl;
dfs2(q[i]);
}
} for (int i= ; i<=cas ; i++){
int x=sccno[edge[i].from],y=sccno[edge[i].to];
if (x==y) continue;
du[x]++;
}
int flag=-,ans;
for (int i= ; i<=scc_cnt ; i++)
if (!du[i]) flag++,ans=sum[i];
if (flag==) printf("%d\n",ans);
else puts("");
return ;
}
Tarjan算法链接也就讲的很清楚了
#include<cstdio>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stack>
using namespace std; const int M = 1e5 + ;
int head[M],cas,scc_cnt,dfs_clock;
int sccno[M],du[M],sum[M],lowlink[M],pre[M];
stack<int>s; int min(int x,int y){return x<y?x:y;} struct Edge{
int to,next,from;
}edge[M*]; void add(int u,int v)
{
edge[++cas].next=head[u];
edge[cas].to=v;edge[cas].from=u;
head[u]=cas;
} void dfs(int u)
{
pre[u]=lowlink[u]=++dfs_clock;
s.push(u);
for (int i=head[u] ; i ; i=edge[i].next){
int v=edge[i].to;
if (!pre[v]){
dfs(v);
lowlink[u]=min(lowlink[u],lowlink[v]);
}
else if (!sccno[v]){
lowlink[u]=min(lowlink[u],pre[v]);
}
}
if (lowlink[u]==pre[u]){
scc_cnt++;
for ( ; ; ){
int x=s.top();s.pop();
sccno[x]=scc_cnt;
if (x==u) break;
}
}
} int main()
{
int n,m;
scanf("%d%d",&n,&m);
cas=,dfs_clock=,scc_cnt=;
while (m--){
int x,y;
scanf("%d%d",&x,&y);
add(x,y);
}
memset(pre,,sizeof(pre));
memset(lowlink,,sizeof(lowlink));
memset(du,,sizeof(du));
memset(sum,,sizeof(sum));
for (int i= ; i<=n ; i++)
if (!pre[i]) dfs(i);
for (int i= ; i<=n ; i++)
sum[sccno[i]]++;
for (int i= ; i<=cas ; i++){
int u=sccno[edge[i].from],v=sccno[edge[i].to];
if (u==v) continue;
du[u]++;
}
int flag=,ans;
for (int i= ; i<=scc_cnt ; i++)
if (!du[i]) flag++,ans=sum[i];
if (flag==) printf("%d\n",ans);
else puts("");
return ;
}
最新文章
- python enumerate用法
- Hadoop学习笔记—11.MapReduce中的排序和分组
- 调试的时候 line not available!
- Ubuntu 12.4 Apache2 安装教程
- iOS宏和__attribute__
- js 两个滚动事件相互影响
- 用SignalR实现的弹幕功能
- 函数指针的一个demo
- KVM虚拟机CPU说明
- Authentication token manipulation error for ubuntu ubuntu-16.04.1-desktop-amd64
- pylons使用多个数据库(multiple DB)
- winform无边框拖动
- oracle常用查询三
- phpStudy下安装memcache扩展
- MVC+EF 入门教程(四)
- BZOJ 4513: [Sdoi2016]储能表 [数位DP !]
- SQL之case when then用法(用于分类统计)
- Building QGIS from source - step by step(随笔2)
- 【mysql】模糊查询的使用
- [转]Servlet的学习之Filter过滤器技术