洛谷 P2661 信息传递（拓扑排序||最小环）

题目链接：https://www.luogu.com.cn/problem/P2661

（最大环：https://www.luogu.com.cn/problem/P5145）

用拓扑排序，将能在拓扑队列中的所有点删掉，即这些点不能在环中，判环。

然后找出在环中的点，进行DFS，搜一遍环看它的sum，取min

AC代码：

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<queue>
 6 using namespace std;
 7 int n,ans=0x7f7f7f,tot;
 8 const int N=200005;
 9 int head[N],in[N],c[N],vis[N],sum;
10 queue<int> q;
11 struct node{
12     int to,next;
13 }edge[N];
14 void add(int u,int v){
15     edge[tot].next=head[u];
16     edge[tot].to=v;
17     head[u]=tot++;
18 }
19 void toposort(){
20     for(int i=1;i<=n;i++) if(in[i]==0) {q.push(i); c[i]=0;}
21     while(!q.empty()){
22         int u=q.front(); q.pop();
23         for(int i=head[u];i!=-1;i=edge[i].next){
24             int v=edge[i].to;
25             in[v]--;
26             if(in[v]==0) {q.push(v); c[v]=0;}
27         }
28     }
29 }
30 void DFS(int u){
31     for(int i=head[u];i!=-1;i=edge[i].next){
32         int v=edge[i].to;
33         if(vis[v]) { ans=min(ans,sum); return;}
34         sum+=1;
35         vis[v]=1;
36         DFS(v);
37     }
38 }
39 int main(){
40     memset(head,-1,sizeof(head));
41     memset(c,1,sizeof(c));
42     scanf("%d",&n);
43     for(int i=1;i<=n;i++){
44         int t;
45         scanf("%d",&t);
46         add(i,t);
47         in[t]++;
48     }
49     toposort();
50     for(int i=1;i<=n;i++){
51         sum=0;
52         if(!vis[i]&&c[i]){
53             DFS(i);
54         }
55     }
56     printf("%d",ans);
57     return 0;
58 }

AC代码