自己打一遍第一题，入门啦，入门啦
题目还算简单，多头牛，给你仰慕关系（可传递），问你最后有没有牛被所有的牛仰慕
根据关系可以建图，利用tarjan算法缩点处理后，得到有向无环图，缩成的点都是相互仰慕的，所以根据传递性也就是可以看成一个点了，然后染色分块，计算每一块的出度。
如果出度为0有且仅有一个，那么输出该块内所有的点，都符合要求
如果有多个直接输出0即可
#include <iostream>
#include <cstdio>
#include <string.h>
using namespace std;
const int maxn = 10005;
const int maxm = 100005;
struct node{
int to,pre;
}e[maxm];
int n,m;
int idx;
int id[maxn],cnt;
int dfn[maxn],low[maxn];
int stack1[maxn],s_top;
int out[maxn];
int color[maxn];
int vis[maxn];
int cut_point = 0;
void init()
{
memset(dfn,0,sizeof(dfn));
memset(vis,0,sizeof(vis));
memset(color,0,sizeof(color));
memset(low,0,sizeof(low));
memset(id,-1,sizeof(id));
memset(out,0,sizeof(id));
cnt = 0;
idx = 0;
s_top = 0;
cut_point = 0;
}
void add(int u,int v)
{
e[cnt].to = v;
e[cnt].pre = id[u];
id[u] = cnt++;
}
void tarjan(int u, int pre)
{
dfn[u] = low[u] = ++idx;
vis[u] = 1;
stack1[s_top++] = u; for(int i = id[u];~i;i = e[i].pre)
{
int v = e[i].to;
if(!vis[v])
{
tarjan(v,u);
low[u] = min(low[v],low[u]);
}
else
{
low[u] = min(low[u],dfn[v]);
}
}
if(low[u] == dfn[u])
{
cut_point++;//颜色1 。。。n
while(s_top > 0 && stack1[s_top] != u)//目的是先处理完元素在判断是不是最后一个
{
s_top--;
vis[stack1[s_top]] = 2;
color[stack1[s_top]] = cut_point;
}
}
} int main()
{
int u,v;
while(~scanf("%d%d",&n,&m))
{
//初始化
init();
//添加边
for(int i = 0;i < m;i++)
{
scanf("%d%d",&u,&v);
add(u,v);
}
//缩点处理——染色
for(int i = 1;i <= n;i++)//防止不连通的情况
{
if(!vis[i])
{
tarjan(i,-1);
}
}
//染色成功后，记录出度
for(int i = 1;i <= n;i++)
{
for(int j = id[i];~j;j = e[j].pre)
{
int v = e[j].to;
if(color[i] != color[v])
{
++out[color[i]];
}
}
}
//看看度为0的点的集合，找出所有的点
//color还要一样，不能有两个
int sum = 0,p_color;
for(int i = 1;i <= cut_point;i++)
{
if(!out[i])
sum++,p_color = i;
} if(sum == 1)
{
int ans = 0;
for(int i = 1;i <= n;i++)
{
if(color[i] == p_color)ans++;
}
printf("%d\n",ans);
}
else
{
puts("0");
}
}
return 0;
}