【图论】强连通分量

一.定义

 强连通分量（Strongly Connected Components，简称SCC）是图论中的一个概念，用于描述有向图中的一组顶点，其中任意两个顶点之间都存在一条有向路径。换句话说，对于图中的任意两个顶点u和v，如果存在一条从u到v的有向路径，同时也存在一条从v到u的有向路径，那么u和v就属于同一个强连通分量。

强连通分量在许多图算法中都有重要的应用，比如强连通分量的计算可以用于解决图的可达性问题、强连通分量的缩点可以用于求解最小生成树等。

注意：强连通分量是有向图！

---

 二.例题

P2661 [NOIP2015 提高组] 信息传递 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

---

三.思路

我们可以易知可以求得最小环即可。也可以说要求最小强连通分量。

这里可以用tarjan算法实现

---

四.参考代码

#include<bits/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;
}
vector<int> 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 i=head[u];i;i=edge[i].next){int v=edge[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 j=0;//已经构成环 if(dfn[u]==low[u]){ls++;while(1){j=sta[--top];ins[j]=0;it[ls].push_back(j);if(u==j) break;}}
}
int main(){scanf("%d",&n);int k;for(int i=1;i<=n;i++){scanf("%d",&k);add(i,k);}for(int i=1;i<=n;i++){if(dfn[i]==0) tarjan(i);}int ans=0x7fffffff;for(int i=1;i<=ls;i++){int x=it[i].size();if(x>1) ans=min(ans,x);}cout<<ans;return 0;
}