题意：奶牛之间互生爱慕，这种感情可以传递，问能被其它所有奶牛喜爱的奶牛头数。
解法：出度为0的连通分量如果为1，则该连通分量中点的个数就是所求，否则输出0。
代码：
#include<iostream>
#include<cstring>
#include<stack>
#include<algorithm>
#include<cstdio>
using namespace std;
const int N = 10005, M = 50005;
struct EdgeT{
int adj;
int next;
};
EdgeT edge[M];
int n,m,head[N],out[N]; //head[i]:顶点i的邻接表头 out[i]:顶点i的出度
int index,scc,dfn[N],low[N],belong[N]; //求强连通分量用
stack<int> s;
bool instack[N];
void init(){
fill(head,head+N,-1);
fill(belong,belong+N,-1);
fill(out,out+N,0);
fill(dfn,dfn+N,-1);
fill(low,low+N,-1);
fill(instack,instack+N,false);
index=scc=0;
}
void tarjan(int u){
int v;
dfn[u]=low[u]=++index;
s.push(u);
instack[u]=true;
for (int i=head[u];i!=-1;i=edge[i].next){
v=edge[i].adj;
if (dfn[v]==-1){
tarjan(v);
low[u]=min(low[u],low[v]);
}else if (instack[v])
low[u]=min(low[u],dfn[v]);
}
if (low[u]==dfn[u]){
scc++;
do{
v=s.top();
s.pop();
instack[v]=false;
belong[v]=scc;
}while (v!=u);
}
}
void solve(){
scanf("%d%d",&n,&m);
for (int i=0,x,y;i<m;i++){
scanf("%d%d",&x,&y);
edge[i].adj=y;
edge[i].next=head[x];
head[x]=i;
}
for (int i=1;i<=n;i++)
if (dfn[i]==-1)
tarjan(i);
for (int i=1;i<=n;i++){
for (int j=head[i];j!=-1;j=edge[j].next)
{
if (belong[i]!=belong[edge[j].adj]){
out[belong[i]]++;
break;
}
}
}
int num=0,popular,ans=0;
for (int i=1;i<=scc;i++)
if (!out[i])
num++,popular=i;
if (num!=1){
printf("0\n");
return;
}
for (int i=1;i<=n;i++)
if (belong[i]==popular)
ans++;
printf("%d\n",ans);
}
int main(){
init();
solve();
return 0;
}
posted on 2015-08-27 23:04
龙在江湖 阅读(173)
评论(0) 编辑 收藏 引用 所属分类:
图论