题目链接：
思路： 题目的意思是说给定一个无向图，求图中的顶点到环上顶点的最短距离（有且仅有一个环，并且环上顶点的距离不计）。
一开始我是直接用Tarjan求的无向图的双连通分量，然后标记连通分量上的点（如果某一个连通分量上的顶点的个数大于1，那么就是环了，其余的都只有一个点），然后即使重新建图，spfa求最短路径。
#include后来我发现自己想的太复杂了，其实只要一遍dfs就能求出这个环上的点了，具体的做法是从某一点开始深搜，然后如果遇上之前搜过的点，那么说明形成一个环，用一个变量记录这个点，然后回退的时候判断是否遇到过这个点，如果没有遇到过，就把回退路径上的点都标记为环上的点，否则，继续回退。最后即使一遍bfs就可以求出最短路径。#include #include #include #include #include #include #define REP(i, a, b) for (int i = (a); i < (b); ++i)#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)using namespace std;const int MAX_N = (3000 + 300);int dfn[MAX_N], low[MAX_N], cnt, N, _count, color[MAX_N];int st, dist[MAX_N];bool mark[MAX_N];vector g[MAX_N], reg[MAX_N];stack S;void Tarjan(int u, int father){ low[u] = dfn[u] = ++cnt; S.push(u); mark[u] = true; REP(i, 0, (int)g[u].size()) { int v = g[u][i]; if (father == v) continue; if (dfn[v] == 0) { Tarjan(v, u); low[u] = min(low[u], low[v]); } else if (mark[v]) { low[u] = min(low[u], dfn[v]); } } if (low[u] == dfn[u]) { int x, num = 0; ++_count; do { x = S.top(); S.pop(); mark[x] = false; color[x] = _count; ++num; } while (x != u); if (num > 1) st = _count; }}void spfa(int st){ queue que; memset(dist, 0x3f, sizeof(dist)); memset(mark, false, sizeof(mark)); dist[st] = 0; que.push(st); while (!que.empty()) { int u = que.front(); que.pop(); REP(i, 0, (int)reg[u].size()) { int v = reg[u][i]; if (dist[u] + 1 < dist[v]) { dist[v] = dist[u] + 1; if (!mark[v]) { mark[v] = true; que.push(v); } } } }}int main(){ while (cin >> N) { FOR(i, 1, N) g[i].clear(), reg[i].clear(); FOR(i, 1, N) { int u, v; cin >> u >> v; g[u].push_back(v); g[v].push_back(u); } cnt = _count = 0; memset(dfn, 0, sizeof(dfn)); memset(mark, false, sizeof(mark)); FOR(i, 1, N) if (!dfn[i]) Tarjan(i, -1); FOR(u, 1, N) { REP(i, 0, (int)g[u].size()) { int v = g[u][i]; if (color[u] != color[v]) reg[color[u]].push_back(color[v]), reg[color[v]].push_back(color[u]); } } spfa(st); FOR(i, 1, N) { cout << dist[color[i]]; if (i == N) cout << endl; else cout << " "; } } return 0;}
#include#include #include #include #include #include #define REP(i, a, b) for (int i = (a); i < (b); ++i)#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)using namespace std;const int MAX_N = (3000 + 300);int N, flag[MAX_N], dist[MAX_N], mark[MAX_N], found, st, Ok;vector g[MAX_N];void dfs(int u, int father){ mark[u] = true; REP(i, 0, (int)g[u].size()) { int v = g[u][i]; if (v == father) continue; if (!mark[v]) dfs(v, u); else { found = 1; st = v; flag[u] = 1; return; } if (found) { if (Ok) return; if (st == u) Ok = 1; flag[u] = 1; return; } }}void bfs(int st){ queue que; memset(mark, false, sizeof(mark)); mark[st] = true; dist[st] = 0; que.push(st); while (!que.empty()) { int u = que.front(); que.pop(); REP(i, 0, (int)g[u].size()) { int v = g[u][i]; if (mark[v]) continue; mark[v] = true; if (flag[v]) dist[v] = 0; else dist[v] = dist[u] + 1; que.push(v); } }}int main(){ while (cin >> N) { FOR(i, 1, N) g[i].clear(), flag[i] = mark[i] = 0; FOR(i, 1, N) { int u, v; cin >> u >> v; g[u].push_back(v); g[v].push_back(u); } found = Ok = 0; dfs(1, 1); bfs(st); FOR(i, 1, N) { cout << dist[i]; if (i == N) cout << endl; else cout << " "; } } return 0;}