题目大意:有n个点,每个点只有一条出边.请问图中节点数大于1的强连通分量最小的节点数是多少(其实也就是图中的最小环路有多大,因为每个点只有一条出边).
刚拿到这道题的时候,我就明白这是基环树(森林)了,大概是这样的题型做多了罢
然后我就写了半天的Tarjan,判断强连通分量,结果发现并不用
代码如下
#include <iostream>
using namespace std;
int po[200011];//每个节点指向的下一个节点
int se[200011];//节点的dfs序
bool bl[200011];//节点"抹除"标记
int minn=1145141919;//答案
//先看函数的传参,node表示当前节点,seq表示dfs序,思想类似于Tarjan
inline void dfs(int node,int seq){
se[node]=seq;//记录节点的dfs序
if(se[po[node]]==0) dfs(po[node],seq+1);//递归遍历,每次都递归到出边的下一个节点
else if(!bl[po[node]]) minn=min(minn,se[node]-se[po[node]]+1);//就像"蛇咬尾",环路的"蛇头"(当前节点)的dfs序-"蛇尾"(还留在栈中的遍历过的节点,其实比喻做"蛇身更恰当")dfs序+1=蛇的长度(即环路大小)
bl[node]=true;//将当前节点标记为在栈外且遍历过,这意味着这个节点类似于被抹除了
}
int main(){
int n;cin >> n;
for(int i=1;i<=n;i++) cin >> po[i];
//以上两行是homoの特有输入格式(大嘘)
for(int i=1;i<=n;i++)
if(!bl[i]) dfs(i,1);//因为是森林,且是有向图,一次遍历是不够的,要写一个循环把所有的点都确保遍历到
cout << minn;//输出答案
return 0;
}
代码略丑,见谅
题目数据:
5
2 4 2 3 1
构图:
(正在施工ing,qwq)