大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺
每一头牛的愿望就是变成一头最受欢迎的牛。
现在有 N 头牛，编号从 1 到 N，给你 M 对整数 (A,B)，表示牛 A 认为牛 B 受欢迎。
这种关系是具有传递性的，如果 A 认为 B 受欢迎，B 认为 C 受欢迎，那么牛 A 也认为牛 C 受欢迎。
你的任务是求出有多少头牛被除自己之外的所有牛认为是受欢迎的。
输入格式
第一行两个数 N,M；
接下来 M 行，每行两个数 A,B，意思是 A 认为 B 是受欢迎的（给出的信息有可能重复，即有可能出现多个 A,B）。
输出格式
输出被除自己之外的所有牛认为是受欢迎的牛的数量。
数据范围
1≤N≤104,
1≤M≤5×104
输入样例：
3 3
1 2
2 1
2 3
输出样例：
1
样例解释
只有第三头牛被除自己之外的所有牛认为是受欢迎的。
题解
Tarjan
#include<bits/stdc++.h>
using namespace std;
const int N = 1e4 + 10;
const int M = 5e4 + 10;
struct Edge{
int v,next,w;
}edge[M];
int head[N],cnt;
int low[N],num[N],dfn;
int sccno[N],sta[N],bcc,top;
bool in_stack[N];
int out[N],Size[N];
void add(int u,int v){
edge[cnt].v = v;
edge[cnt].next = head[u];
head[u] = cnt ++;
}
void Tarjan(int u){
low[u] = num[u] = ++ dfn;
sta[top ++] = u,in_stack[u] = true;
for(int i = head[u];~i;i = edge[i].next){
int v = edge[i].v;
if(!num[v]){
Tarjan(v);
low[u] = min(low[u],low[v]);
}
else if(in_stack[v])
low[u] = min(low[u],num[v]);
}
if(low[u] == num[u]){
bcc ++;
int t;
do{
Size[bcc] ++;
t = sta[-- top];
in_stack[t] = false;
sccno[t] = bcc;
}while(t != u);
}
}
int main(){
memset(head,-1,sizeof head);
int n,m;
cin>>n>>m;
int x,y;
for(int i = 0;i < m;i ++){
cin>>x>>y;
add(x,y);
}
for(int i = 1;i <= n;i ++){
if(!num[i])Tarjan(i);
}
for(int i = 1;i <= n;i ++){
for(int j = head[i];~j;j = edge[j].next){
int a = sccno[i],b = sccno[edge[j].v];
if(a != b)out[a] ++;
}
}
int count = 0;
int c = 0;
for(int i = 1;i <= bcc;i ++){
if(!out[i]){
c ++;
count += Size[i];
}
}
if(c == 1)cout<<count<<endl;
else cout<<0<<endl;
return 0;
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/168619.html原文链接：https://javaforall.net
