Codeforces 131D Subway（找图上唯一环）

 

找唯一环的话，用类似拓扑排序的方法，由于环上点的度>=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_pair  
using 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;  
}  

 

补充：软件开发 , C++ ,