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;}