题意
给你一个联通图，问你最少要添加多少条边才能把这个图变成一个双联通图。
思路
非常经典的边双联通分量缩点问题。找出图中所有的边双联通分量，把这些分量各自收缩为一个点，节点之间若有边，一定是割边，这样就得到了一棵由边联通分量缩成的点和割边组成的树，把一个树变成双联通图要添加的最少边数是(r+1)/2其中r是这棵树的节点数量，这是一个蛮重要的结论。
找边联通分量的方法有好多，可以找到所有割边之后，对于每个点启动一次dfs，搜索中屏蔽掉所有割边，这样就可以收割所有的边双联通分量，也可以对于每个点直接启动一次tarjan算法，在函数返回的过程中，收割掉所有low值一样的节点就可以得到边双联通分量。这份代码使用的是后一种方案。
代码
两个题一个数据中有重边，一个没有，这份代码考虑了这个问题，所以连边都能顺利过，双倍经验。
|
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 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 |
// // POJ3552.cpp // playground // // Copyright © 2015 Adam Chang. All rights reserved. // #include <iostream> #include <iomanip> #include <algorithm> #include <queue> #include <vector> #include <set> #include <stack> #include <map> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <ctime> #include <cmath> using namespace std; const int MAXN = 1005; int n = 0, m = 0; vector<int> to[MAXN]; vector<int> to2[MAXN]; void add_edge(int a, int b){ to[a].push_back(b); to[b].push_back(a); } void add_edge2(int a, int b){ to2[a].push_back(b); to2[b].push_back(a); } void remove_duplicate(vector<int> *to){ for (int i = 1; i <= n; i++) { sort(to[i].begin(), to[i].end()); to[i].erase(unique(to[i].begin(), to[i].end()), to[i].end()); } } int sdcc_belong[MAXN]; stack<int> sdcc_stk; int sdcc_dfn[MAXN]; int sdcc_low[MAXN]; vector<vector<int> > sdcc; int sdcc_cnt = 0; void sdcc_tarjan(int cur, int par){ sdcc_dfn[cur] = sdcc_low[cur] = sdcc_cnt++; sdcc_stk.push(cur); for (int i = 0; i < to[cur].size(); i++) { int nxt = to[cur][i]; if (nxt == par) { continue; } if (!sdcc_dfn[nxt]) { //如果对面点还没有进入过，那就进去 sdcc_tarjan(nxt, cur); sdcc_low[cur] = min(sdcc_low[cur], sdcc_low[nxt]); }else { //如果对面点进去过，那么考虑是不是回边，如果是的话要更新当前节点low值 sdcc_low[cur] = min(sdcc_low[cur], sdcc_dfn[nxt]); } } //我们这样处理问题不会受重边影响，因为我们考虑的中心是边联通分量内部的点而非外部的割点，这样我们只需要关心当前这个点及其联通部分是不是有指向之前的点的回边就可以，只要没有回边，就说明边双联通分量已经走完了，可以收割 if (sdcc_low[cur] == sdcc_dfn[cur]) { //当前节点及其联通部分没有任何指向父亲部分的回边了，可以收割和当前节点连着的所有节点为一个双联通分量了 //generate sdcc int last; sdcc.push_back(vector<int>()); int sdccid = (int)sdcc.size(); do{ last = sdcc_stk.top(); sdcc_stk.pop(); sdcc[sdccid-1].push_back(last); sdcc_belong[last] = sdccid; }while (cur != last); } } void get_sdcc(){ memset(sdcc_belong, 0, sizeof(sdcc_belong)); while (!sdcc_stk.empty()) { sdcc_stk.pop(); } memset(sdcc_dfn, 0, sizeof(sdcc_dfn)); memset(sdcc_low, 0, sizeof(sdcc_low)); sdcc.clear(); sdcc_cnt = 0; for (int i = 1; i <= n; i++) { if (!sdcc_dfn[i]) { sdcc_tarjan(i,0); } } } int main(){ scanf(" %d %d",&n, &m); for (int i = 1; i <= n; i++) { to[i].clear(); } for (int i = 1; i <= m; i++) { int a = 0, b = 0; scanf(" %d %d",&a, &b); add_edge(a, b); } get_sdcc(); for (int i = 1; i <= n; i++) { for (int j = 0; j < to[i].size(); j++) { if (sdcc_belong[to[i][j]] != sdcc_belong[i]) { add_edge2(sdcc_belong[to[i][j]], sdcc_belong[i]); } } } remove_duplicate(to2); int res = 0; for (int i = 1; i <= n; i++) { if (to2[i].size() == 1) { res++; } } cout << (res+1)/2 << endl; return 0; } |
