受欢迎的牛
题目描述
原题来自:USACO 2003 Fall
每一头牛的愿望就是变成一头最受欢迎的牛。现在有
输入格式
第一行两个数
接下来
(给出的信息有可能重复,即有可能出现多个
输出格式
输出被除自己之外的所有牛认为是受欢迎的牛的数量。
输入
3 3
1 2
2 1
2 3
输出
1
Notes:只有第三头牛被除自己之外的所有牛认为是受欢迎的。
题解
受欢迎的奶牛只有可能是
- 图中唯一的出度为零的强连通分量中的所有奶牛,
若出现两个以上出度为 0 的强连通分量
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 10010;
int n, m, dfn[N], low[N], instk[N], siz[N], top, tot, cnt, scc[N], stk[N], cdu[N];
vector<int> e[N];
void tarjan(int x)
{
dfn[x] = low[x] = ++tot;
stk[++top] = x;
instk[x] = 1;
for (int y : e[x])
{ //邻接表存图
if (!dfn[y])
{
tarjan(y);
low[x] = min(low[x], low[y]);
}
else if (instk[y])
{
low[x] = min(low[x], low[y]);
}
}
if (dfn[x] == low[x])
{
int y;
++cnt;
do
{
y = stk[top--];
instk[y] = 0;
scc[y] = cnt;
++siz[cnt];
} while (y != x);
}
}
int main()
{
ios::sync_with_stdio(false), cin.tie(nullptr);
cin >> n >> m;
for (int i = 1; i <= m; i++)
{
int a, b;
cin >> a >> b;
e[a].push_back(b);
}
for (int i = 1; i <= n; i++)
{
if (!dfn[i])
tarjan(i);
}
/*---------------核心代码--------------------*/
//记录强连通分量的出度
for (int x = 1; x <= n; x++)
for (int y : e[x])
if (scc[x] != scc[y])
cdu[scc[x]]++;//rdu[scc[y]]++;
int ans = 0;
for (int i = 1; i <= cnt; i++)
{
if(!cdu[i])
{
if(ans)
{
cout << 0 << '\n';//出现两个以上出度为 0 的强连通分量
return 0;
}
ans = i;
}
}
cout << siz[ans] << '\n';//输出该强连通分量的大小
/*---------------核心代码--------------------*/
}