Light OJ 1291 Real Life Traffic 双连通最少添边数

Light OJ 1291 Real Life Traffic 双连通最少添边数

题目来源：Light OJ 1291 Real Life Traffic

题意：最少添加几条边 可以使全图边双连通

思路：缩点 重新构图 答案就是（叶子节点数+1）/ 2

#include <vector>
#include <cstdio>
#include <cstring>
#include <stack>
#include <algorithm>
using namespace std;
const int maxn = 10010;
struct Edge
{int u, v;Edge(){}Edge(int u, int v): u(u), v(v){}
};
vector <int> a[maxn];
int pre[maxn];
int low[maxn];
int bccno[maxn];
int dfs_clock;
int bcc_cnt;
int bri;
int n, m;
int degree[maxn];
stack <int> S;void dfs(int u, int fa)
{low[u] = pre[u] = ++dfs_clock;S.push(u);for(int i = 0; i < a[u].size(); i++){int v = a[u][i];if(v == fa)continue;if(!pre[v]){dfs(v, u);low[u] = min(low[u], low[v]);}else if(v != fa)low[u] = min(low[u], pre[v]);}if(low[u] == pre[u]){bcc_cnt++;while(1){int x = S.top(); S.pop();bccno[x] = bcc_cnt;if(x == u)break;}}
}
void find_bcc()
{memset(pre, 0, sizeof(pre));memset(bccno, 0, sizeof(bccno));dfs_clock = bcc_cnt = bri = 0;for(int i = 0; i < n; i++)if(!pre[i])dfs(i, -1);
}
int main()
{int cas = 1;int T;scanf("%d", &T);while(T--){scanf("%d %d", &n, &m);for(int i = 0; i <= n; i++)a[i].clear();while(m--){int u, v;scanf("%d %d", &u, &v);a[u].push_back(v);a[v].push_back(u);}find_bcc();memset(degree, 0, sizeof(degree));for(int u = 0; u < n; u++){for(int i = 0; i < a[u].size(); i++){int v = a[u][i];if(bccno[u] != bccno[v]){degree[bccno[u]]++;degree[bccno[v]]++;}}}int ans = 0;for(int i = 1; i <= bcc_cnt; i++)if(degree[i] == 2)ans++;printf("Case %d: %dn", cas++, (ans+1)/2);}return 0;
}