87 lines
2.5 KiB
C++
87 lines
2.5 KiB
C++
#include <bits/stdc++.h>
|
||
|
||
using namespace std;
|
||
const int INF = 0x3f3f3f3f;
|
||
//拓扑排序+链接式前向星实现
|
||
/**
|
||
思路：其实就是求最小环。每个点的出度都是1，因此构成的图要么是一条链+一个环，要么是几个环，通过拓扑可以消去链状的部分，
|
||
对环的部分dfs算最小环即可。
|
||
*/
|
||
const int N = 2e5 + 10;
|
||
|
||
int n, idx, ans = INF;
|
||
int head[N]; //链表头数组
|
||
|
||
int in[N]; //入度数组
|
||
queue<int> q; //拓扑排序用的队列
|
||
|
||
struct Edge {
|
||
int to, next;
|
||
} edge[N]; //边数，也不可能多于结点数，因为这里是指每个结点引出的边数集合
|
||
|
||
bool st[N];
|
||
|
||
//从u向v连一条边，本题无权值概念,头插法
|
||
void add(int u, int v) {
|
||
// 进来先++是非常优美的操作，省去了初始化head[i]=-1!~~~,不过注意，遍历的方式有所变动,第二个条件是i,而不是i!=-1
|
||
edge[++idx].to = v; //因为idx默认值是，进来先++，就是第一个可用值是edge[1],edge[0]丢弃不使用的意思
|
||
edge[idx].next = head[u];
|
||
head[u] = idx;
|
||
//入度++
|
||
in[v]++;
|
||
}
|
||
|
||
//拓扑排序
|
||
void topsort() {
|
||
//入度为0的结点入队列，进行拓扑排序
|
||
for (int i = 1; i <= n; i++) if (!in[i]) q.push(i);
|
||
|
||
//拓扑排序
|
||
while (!q.empty()) {
|
||
int u = q.front();
|
||
q.pop();
|
||
//不是环中结点
|
||
st[u] = true;
|
||
//遍历每条出边
|
||
for (int j = head[u]; j; j = edge[j].next) {
|
||
int y = edge[j].to;
|
||
if (!--in[y]) q.push(y);//在删除掉当前结点带来的入度后，是不是入度为0了，如果是将点y入队列
|
||
}
|
||
}
|
||
}
|
||
|
||
/**
|
||
功能：求DAG中包含点u的环的长度
|
||
参数： u 结点
|
||
len 长度
|
||
*/
|
||
void dfs(int u, int len) {
|
||
//标识探测过了
|
||
st[u] = true;
|
||
//遍历所有u开头的边
|
||
for (int i = head[u]; i; i = edge[i].next) {
|
||
int y = edge[i].to;
|
||
//如果这个点还没有被探测过,那么，计算长度
|
||
if (!st[y]) dfs(y, ++len);
|
||
else { //到这里是发现了环！
|
||
ans = min(ans, len);
|
||
return; //第一次发现的就是终点
|
||
}
|
||
}
|
||
}
|
||
|
||
int main() {
|
||
cin >> n;
|
||
for (int u = 1; u <= n; u++) {
|
||
int x;
|
||
cin >> x;
|
||
add(u, x);
|
||
}
|
||
//拓扑排序
|
||
topsort();
|
||
|
||
//到这里，st[i]=false的就应该是环中结点,对环的部分dfs算最小环即可
|
||
for (int i = 1; i <= n; i++) if (!st[i]) dfs(i, 1);
|
||
cout << ans << endl;
|
||
}
|