Codeforces 131D Subway（找图上唯一环）
给定一个n个点n条边存在唯一环的联通图，求每个点到环的距离。
找唯一环的话，用类似拓扑排序的方法，由于环上点的度>=2，所以bfs后未能遍历的点必在环上，然后就用dfs跟新距离就行了。
#include<algorithm>#include<iostream>#include<cstring>#include<fstream>#include<sstream>#include<cstdlib>#include<vector>#include<string>#include<cstdio>#include<bitset>#include<queue>#include<stack>#include<cmath>#include<map>#include<set>#define FF(i, a, b) for(int i=a; i<b; i++)#define FD(i, a, b) for(int i=a; i>=b; i--)#define REP(i, n) for(int i=0; i<n; i++)#define CLR(a, b) memset(a, b, sizeof(a))#define debug puts("**debug**")#define LL long long#define PB push_back#define MP make_pairusing namespace std;const int maxn = 3010;int n, u, v, dist[maxn], degree[maxn];bool vis[maxn];vector<int> G[maxn];void bfs(){ queue<int> q; FF(i, 1, n+1) if(degree[i] == 1) q.push(i); while(!q.empty()) { int x = q.front(); q.pop(); vis[x] = 1; REP(i, G[x].size()) { int v = G[x][i]; if(!vis[v]) { degree[v]--; if(degree[v] < 2) q.push(v); } } }}void dfs(int u, int fa){ REP(i, G[u].size()) { int v = G[u][i]; if(v != fa && vis[v]) { dist[v] = dist[u] + 1; dfs(v, u); } }}int main(){ scanf("%d", &n); FF(i, 1, n+1) { scanf("%d%d", &u, &v); G[u].PB(v); G[v].PB(u); degree[u]++; degree[v]++; } bfs(); FF(i, 1, n+1) if(!vis[i]) dfs(i, -1); FF(i, 1, n+1) printf("%d ", dist[i]); return 0;}