Codeforces Beta Round #95 (Div. 2) D : Subway
問題概要
ノード数V(<3000)、辺数Vの連結な無向グラフが与えられる。当然環状な部分が一つできるが、それを一つの頂点に潰したグラフで、潰した頂点からの各点への距離を全て求める問題。
解法
頂点を潰した後は木になるので距離は簡単に求められる。問題は環を潰す部分。次数1の頂点を見つけて減らしていけば残ったのが環になる。
本番で通ったコード
計算量O(V^2)。
#include <cstdio> #include <vector> #include <queue> #include <algorithm> using namespace std; const int MAX_N = 3000; const int INF = 1<<29; int N; vector<int> graph[MAX_N]; bool visited[MAX_N]; int degree[MAX_N]; int dist[MAX_N]; void solve(){ for(int i=0; i<N; i++){ for(int j=0; j<N; j++)if(degree[j] == 1){ for(int k=0; k<(int)graph[j].size(); k++){ degree[graph[j][k]]--; } degree[j] = 0; } } fill(dist, dist + N, INF); queue<int> que; for(int i=0; i<N; i++)if(degree[i] > 0){ dist[i] = 0; visited[i] = true; que.push(i); } while(!que.empty()){ int v = que.front(); que.pop(); for(int i=0; i<graph[v].size(); i++){ int u = graph[v][i]; if(!visited[u]){ visited[u] = true; dist[u] = dist[v] + 1; que.push(u); } } } for(int i=0; i<N; i++){ printf("%d%c", dist[i], i==N-1?'\n':' '); } } int main(){ scanf("%d", &N); for(int i=0; i<N; i++){ int x, y; scanf("%d%d", &x, &y); x--; y--; graph[x].push_back(y); graph[y].push_back(x); degree[x]++; degree[y]++; } solve(); return 0; }