济南市历下区建设局官方网站,网站建设服务预算,毕节市生态文明建设网站,wordpress图片放大镜一.作用
强连通分量可以判断环和进行缩点。还有一系列作用....
这篇文章介绍缩点 二.题目
https://www.luogu.com.cn/problem/P2341 三.思路
我们分析可以知道当一个点没有出度时#xff0c;则为最受欢迎的牛。但如果有多个出度#xff0c;则没有最受欢迎的牛。
这是只有…一.作用
强连通分量可以判断环和进行缩点。还有一系列作用....
这篇文章介绍缩点 二.题目
https://www.luogu.com.cn/problem/P2341 三.思路
我们分析可以知道当一个点没有出度时则为最受欢迎的牛。但如果有多个出度则没有最受欢迎的牛。
这是只有一个出度的情况 这是多个出度的情况 但为什么要判断环对环缩点呢 四.代码实现
只是微改基础是
【图论】强连通分量_SY奇星的博客-CSDN博客
#includebits/stdc.h
#define maxn 50005
using namespace std;
int n,m;
int head[maxn],cnt;
struct Edge{int u,v,next;
}edge[maxn];
void add(int u,int v){edge[cnt](Edge){u,v,head[u]}; head[u]cnt;
}
vectorint it[maxn];
int ls,l[maxn],out[maxn];//有多少环 ,这个数属于哪个环,点的出度
int dfn[maxn],low[maxn],tot;
int sta[maxn],ins[maxn],top;
void tarjan(int u){dfn[u]low[u]tot;sta[top]u;ins[u]1;for(int ihead[u];i;iedge[i].next){int vedge[i].v;if(dfn[v]0){tarjan(v);low[u]min(low[u],low[v]);}else if(ins[v]){low[u]min(low[u],dfn[v]);}}int j0;if(dfn[u]low[u]){ls;while(1){jsta[--top];ins[j]0;it[ls].push_back(j);l[j]ls; //缩点 即一个点属于哪个环或者说是哪个缩点。 if(uj) break;}}
}
int main(){scanf(%d%d,n,m);int u,v;for(int i1;im;i){scanf(%d%d,u,v);add(u,v);}for(int i1;in;i){if(dfn[i]0) tarjan(i);}for(int i1;in;i){for(int jhead[i];j;jedge[j].next){int vedge[j].v;if(l[i]!l[v]){out[l[i]]; //出度 }}}int ans0;for(int i1;ils;i){if(out[i]0){if(ans0) ansi;else{cout0; return 0;} }}coutit[ans].size();return 0;
}
