CFR 131 D. Subway ( 水母圖 DFS )

Problem - 131D - Codeforces
n個點 n條邊保證聯通，俗稱的水母圖。題目求的是每個點與環的距離，所以用一次 dfs求環，利用 next數組就能夠紀錄並判環。最後再把所有環裡的點拿去做bfs求距離。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 3e3 + 3;

int n;
vector< int > G[ MAXN ];

int nxt[ MAXN ];
int findAnyInCycle( int u, int fa ){
    for( int v : G[ u ] ){
        if( v == fa ) continue;
        nxt[ u ] = v;
        if( nxt[ v ] != -1 ) return v;
        int res = findAnyInCycle( v, u );
        if( res ) return res;
    }
    return 0;
}

int dis[ MAXN ];

void solve(){
    memset( nxt, -1, sizeof(nxt) );
    int _u = findAnyInCycle( 1, -1 );
    queue< int > que;
    memset( dis, 0x3f3f3f3f, sizeof(dis) );
    for( int u = _u; ; ){
        que.push( u );
        dis[ u ] = 0;
        u = nxt[ u ];
        if( u == _u ) break;
    }
    while( !que.empty() ){
        int u = que.front();
        que.pop();
        for( int v : G[ u ] ){
            if( dis[ v ] > dis[ u ] + 1 )
                dis[ v ] = dis[ u ] + 1,
                que.push( v );
        }
    }
    for( int u = 1; u <= n; ++u )
        printf("%d%c", dis[ u ], u == n ? '\n' : ' ');
}

int main(){
    scanf("%d", &n);
    for( int i = 0; i < n; ++i ){
        int u, v; scanf("%d%d", &u, &v);
        G[ u ].push_back( v );
        G[ v ].push_back( u );
    }
    solve();
    return 0;
}