题解：AT_code_festival_relay_f ループを探せ

题意

给你一个 $n$ 个点，$n$ 个边的无向联通图，让你找到这个图中环的长度

思路

众所周知，拓扑排序对于无环图可以遍历，那么没被遍历到的肯定就是环中的元素。

考虑对于图进行拓扑排序。记录每次遍历到的点，用 $n$ 减去遍历过的节点即可。

代码

#include<bits/stdc++.h>
using namespace std;
int n,ans;
vector<int> g[100005];//这里使用vector邻接表来存图
int d[100005];
bool vis[100005];
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		int x,y;
		cin>>x>>y;
		d[x]++,d[y]++;
		g[x].push_back(y);
		g[y].push_back(x);
		//加边
	}
	queue<int> q;
	//找到第一次拓扑排序的点
	for(int i=1;i<=n;i++){
		if(d[i]==1){
			q.push(i);
			vis[i]=1;
		}
	}
	//拓扑排序过程
	while(q.size()){
		int t=q.front();
		q.pop();
		ans++;//计算遍历过的点的数量
		for(auto v:g[t]){
			if(vis[v])continue;
			d[v]--;
			if(d[v]==1){
				q.push(v);
				vis[v]=1;
				//找到下一次遍历的节点
			}
		}
	}
	cout<<n-ans;
	cout<<endl;//注意这里，Atcoder早期题目末尾必须加上这个
	return 0;
}

TIPS

冷知识，Atcoder 前期比赛的输出末尾是要加上换行的，如果你没有加上，那么恭喜你，你将会全部答案错误。