1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91
|
#include<cstdio> #include<cstring> #include<algorithm> #include<vector> using namespace std; const int SIZE = 100010; int head[SIZE], ver[SIZE * 2], Next[SIZE * 2]; int dfn[SIZE], low[SIZE], stack[SIZE], new_id[SIZE], c[SIZE]; int n, m, tot, num, root, top, cnt, tc; bool cut[SIZE]; vector<int> dcc[SIZE]; int hc[SIZE], vc[SIZE * 2], nc[SIZE * 2];
void (int x, int y) { ver[++tot] = y, Next[tot] = head[x], head[x] = tot; }
void add_c(int x, int y) { vc[++tc] = y, nc[tc] = hc[x], hc[x] = tc; }
void tarjan(int x) { dfn[x] = low[x] = ++num; stack[++top] = x; if (x == root && head[x] == 0) { dcc[++cnt].push_back(x); return; } int flag = 0; for (int i = head[x]; i; i = Next[i]) { int y = ver[i]; if (!dfn[y]) { tarjan(y); low[x] = min(low[x], low[y]); if (low[y] >= dfn[x]) { flag++; if (x != root || flag > 1) cut[x] = true; cnt++; int z; do { z = stack[top--]; dcc[cnt].push_back(z); } while (z != y); dcc[cnt].push_back(x); } } else low[x] = min(low[x], dfn[y]); } }
int main() { cin >> n >> m; tot = 1; for (int i = 1; i <= m; i++) { int x, y; scanf("%d%d", &x, &y); if (x == y) continue; add(x, y), add(y, x); } for (int i = 1; i <= n; i++) if (!dfn[i]) root = i, tarjan(i); for (int i = 1; i <= n; i++) if (cut[i]) printf("%d ", i); puts("are cut-vertexes"); for (int i = 1; i <= cnt; i++) { printf("v-DCC #%d:", i); for (int j = 0; j < dcc[i].size(); j++) printf(" %d", dcc[i][j]); puts(""); } num = cnt; for (int i = 1; i <= n; i++) if (cut[i]) new_id[i] = ++num; tc = 1; for (int i = 1; i <= cnt; i++) for (int j = 0; j < dcc[i].size(); j++) { int x = dcc[i][j]; if (cut[x]) { add_c(i, new_id[x]); add_c(new_id[x], i); } else c[x] = i; } printf("缩点之后的森林,点数 %d,边数 %dn", num, tc / 2); printf("编号 1~%d 的为原图的v-DCC,编号 >%d 的为原图割点n", cnt, cnt); for (int i = 2; i < tc; i += 2) printf("%d %dn", vc[i ^ 1], vc[i]); }
|
近期评论