题目大意:给出N头牛,有M种关系u, v。代表u牛崇拜v牛。要求找出有多少头牛被所有牛崇拜着
题目链接:http://poj.org/problem?id=2186
解题思路:
1>求出强连通分量,标记每头牛属于哪个分量内
2>进行缩点,计算连通分量的个数x,给出的M组关系重新构图。u,v若属不于一个连通分量内out[belong[u]]++;
3>统计x个连通分量出度。如果超过1个的连通分量出度为0,证明两群牛互不崇拜;
如果等于1 答案就是该分量中牛的个数.
代码如下:
#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;
#define N 10005
#define M 50005
struct Edge
{
int v, next;
}edge[M];int node[N], stack[N], instack[N], dfn[N], out[N];
int low[N], belong[N], index, cnt_edge, n, m, cnt_tar, top;
int ee[M][];void add_Edge(int u, int v)
{
edge[cnt_edge].next=node[u];
edge[cnt_edge].v=v;
node[u]=cnt_edge++;
}
void tarjan(int u)
{
int i, j, v;
dfn[u]=low[u]=++index;
stack[++top]=u;
instack[u]=;
for(i=node[u]; i!=-; i=edge[i].next)
{
v=edge[i].v;
if(!dfn[v])
{
tarjan(v);
low[u]=min(low[u], low[v]);
}
else if(instack[v])
low[u]=min(low[u], dfn[v]);
}
if(dfn[u]==low[u])
{
cnt_tar++;
do
{
j=stack[top--];
instack[j]=;
belong[j]=cnt_tar;
}while(j!=u);
}}
void solve()
{
int i;
top=, index=, cnt_tar=;
memset(dfn, , sizeof(dfn));
memset(low, , sizeof(low));
for(i=; i<=n; i++)
if(!dfn[i])
tarjan(i);
}
int main()
{
int i, u, v;
while(scanf("%d%d", &n, &m)!=EOF)
{
cnt_edge=;
memset(node, -, sizeof(node));
for(i=; i<=m; i++)
{
scanf("%d%d", &u, &v);
ee[i][]=u, ee[i][]=v;
add_Edge(u, v);
}
solve();
for(i=; i<=m; i++)
{
int xx=belong[ee[i][]], yy=belong[ee[i][]];
if(xx!=yy)
out[xx]++;
}
int mark=, tot=;
for(i=; i<=cnt_tar; i++)
if(out[i]==)
{
tot++;
mark=i;
}
if(tot>)
printf("0\n");
else if(tot==)
{
tot=;
for(i=; i<=n; i++)
if(belong[i]==mark)
tot++;
printf("%d\n", tot);
}
}
return ;
}