Codeforces 131D Subway（找图上唯一环） - c++编程基础

给定一个n个点n条边存在唯一环的联通图，求每个点到环的距离。

找唯一环的话，用类似拓扑排序的方法，由于环上点的度>=2，所以bfs后未能遍历的点必在环上，然后就用dfs跟新距离就行了。

#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#define FF(i, a, b) for(int i=a; i=b; i--)  
#define REP(i, n) for(int i=0; i G[maxn];  
  
void bfs()  
{  
    queue




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