网站建设与管理 孙伟,seo研究中心好客站,淄博软件开发公司有哪些,编程跟做网站一.定义 强连通分量#xff08;Strongly Connected Components#xff0c;简称SCC#xff09;是图论中的一个概念#xff0c;用于描述有向图中的一组顶点#xff0c;其中任意两个顶点之间都存在一条有向路径。换句话说#xff0c;对于图中的任意两个顶点u和v#xff0c;…一.定义 强连通分量Strongly Connected Components简称SCC是图论中的一个概念用于描述有向图中的一组顶点其中任意两个顶点之间都存在一条有向路径。换句话说对于图中的任意两个顶点u和v如果存在一条从u到v的有向路径同时也存在一条从v到u的有向路径那么u和v就属于同一个强连通分量。
强连通分量在许多图算法中都有重要的应用比如强连通分量的计算可以用于解决图的可达性问题、强连通分量的缩点可以用于求解最小生成树等。
注意强连通分量是有向图 二.例题
P2661 [NOIP2015 提高组] 信息传递 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 三.思路
我们可以易知可以求得最小环即可。也可以说要求最小强连通分量。
这里可以用tarjan算法实现 四.参考代码
#includebits/stdc.h
#define maxn 200005
using namespace std;
int n,dfn[maxn],low[maxn],tot;
//链式前向星
int cnt,head[maxn];
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 sta[maxn],ins[maxn],top,ls; //栈和是否入栈
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);if(uj) break;}}
}
int main(){scanf(%d,n);int k;for(int i1;in;i){scanf(%d,k);add(i,k);}for(int i1;in;i){if(dfn[i]0) tarjan(i);}int ans0x7fffffff;for(int i1;ils;i){int xit[i].size();if(x1) ansmin(ans,x);}coutans;return 0;
}
