双连通分量入门——UVALive - 5135
无向图的双连通分量分为点双连通分量和边双连通分量，从定义上讲就是任意两条至少存在点不重复或者边不重复的路径，应用意义上来讲就是对于一个（点/边）双连通分量来说，删去（一个点/一条边）之后剩下的部分的连通性并没有受到影响，剩下的任意点之前还能互相到达，这就能衍生出很多应用了。
图论中的割点，割边，双连通分量，强连通分量等类型的题目都有比较简单易懂的dfs的算法，看起来也比较相似。
int dfs(int u, int fa){ int lowu = PRe[u] = ++clock; int child = 0; for (int i = 0; i < e[u].size(); i++){ int v = e[u][i]; if (!pre[v]){ s.push({ u, v }); int lowv = dfs(v, u); lowu = min(lowu, lowv); if (lowv >= pre[u]){ is[u] = 1; bcc_cnt++; bcc[bcc_cnt].clear(); while (1){ pair<int, int> x = s.top(); s.pop(); if (bccno[x.first] != bcc_cnt){ bccno[x.first] = bcc_cnt; bcc[bcc_cnt].push_back(x.first); } if (bccno[x.second] != bcc_cnt){ bccno[x.second] = bcc_cnt; bcc[bcc_cnt].push_back(x.second); } if (x.first == u&&x.second == v)break; } } } else if (pre[v]<pre[u]&&v != fa){ s.push({ u, v }); lowu = min(lowu, pre[v]); } } if (fa < 0 && child == 1){ is[u] = 0; } low[u] = lowu; return lowu; } void find_bcc(int n){ memset(pre, 0, sizeof(pre)); memset(is, 0, sizeof(is)); memset(bccno, 0, sizeof(bccno)); clock = bcc_cnt = 0; for (int i = 0; i < n; i++){ if (!pre[i])dfs(i,-1); } }这样处理完之后我们便能获得bcc_cnt个双连通分量，继而根据问题进行下一步处理。
Mining Your Own Business UVALive - 5135
问题描述：矿井由隧道和连接点连接而成，因为有塌方的危险，需要在某些连接点处安装安全井，我们要找出最小需要安装多少个安全井以及方案数。 1.简单来说题目要满足的就是不管哪一个点塌方，其他点都有通路通向安全井。如果图中存在割点，如果割点处塌方，便会出现新的连通分量，这部分孤立的子图若没有安全井，就跑不出去了。 2.所以我们的主要思路就是求出双连通分量，对每一个双连通分量进行处理，若这个双连通分量只由一个割点，就需要在这个连通分量非割点的地方安装一个安全井（割点塌方就直接去所在安全井，安全井塌方就从割点去其他双连通块）。若有不止一个割点，不管哪里塌方了都可以通过一个割点去其他双连通块，所以不用安装。 3.若图本身就是一个双连通分量，因为安全井所在的地方也有可能塌方 ，所以需要安装两个安全井。
#include <iostream> #include <stdio.h> #include <string.h> #include <string> #include <stack> #include <queue> #include <map> #include <set> #include <vector> #include <math.h> #include <bitset> #include <list> #include <algorithm> #include <climits> using namespace std; #define inf 0x3f3f3f3f const int maxn = 50005; int n, m; vector<int> e[maxn]; vector<int> bcc[maxn]; stack<pair<int, int> > s; int pre[maxn]; int low[maxn]; int deg[maxn]; int is[maxn]; int bccno[maxn]; int bcc_clock,bcc_cnt; int dfs(int u, int fa){ int lowu = pre[u] = ++bcc_clock; int child = 0; for (int i = 0; i < e[u].size(); i++){ int v = e[u][i]; if (!pre[v]){ s.push({ u, v }); child++; int lowv = dfs(v, u); lowu = min(lowu, lowv); if (lowv >= pre[u]){ is[u] = 1; bcc_cnt++; bcc[bcc_cnt].clear(); while (1){ pair<int, int> x = s.top(); s.pop(); if (bccno[x.first] != bcc_cnt){ bccno[x.first] = bcc_cnt; bcc[bcc_cnt].push_back(x.first); } if (bccno[x.second] != bcc_cnt){ bccno[x.second] = bcc_cnt; bcc[bcc_cnt].push_back(x.second); } if (x.first == u&&x.second == v)break; } } } else if (pre[v]<pre[u]&&v != fa){ s.push({ u, v }); lowu = min(lowu, pre[v]); } } if (fa < 0 && child == 1){ is[u] = 0; } low[u] = lowu; return lowu; } void find_bcc(int n){ memset(pre, 0, sizeof(pre)); memset(is, 0, sizeof(is)); memset(bccno, 0, sizeof(bccno)); bcc_clock = bcc_cnt = 0; for (int i = 0; i < n; i++){ if (!pre[i])dfs(i,-1); } } int main(){ int x, y; int cas = 0; while (scanf("%d", &m), m){ cas++; n = 0; for (int i = 0; i < maxn; i++){ e[i].clear(); } for (int i = 0; i < m; i++){ scanf("%d%d", &x, &y); n = max(n, max(x, y)); x--, y--; e[x].push_back(y); e[y].push_back(x); } find_bcc(n); long long ans1 = 0, ans2 = 1; if (bcc_cnt == 1){ ans1 = 2; ans2 = (long long)n*(n - 1) / 2; } else{ for (int i = 1; i <= bcc_cnt; i++){ int cut_cnt = 0; for (int j = 0; j < bcc[i].size(); j++){ if (is[bcc[i][j]])cut_cnt++; } if (cut_cnt == 1){ ans1++; ans2 *= (long long)(bcc[i].size() - 1); } } } printf("Case %d: %lld %lld\n", cas, ans1, ans2); } return 0; }