题目大意:求要连多少条边能消除无向图的桥
解题思路:求出图的双向连通子图,每个子图缩点,形成的树有多少个叶子节点,添加的边就为叶子节点数加1除以2
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> using namespace std; struct node { int v, next; }; const int maxn = 1010; int head[maxn], dfn[maxn], low[maxn], degree[maxn], n, m, num, index, e; node edge[maxn]; void addEdge(int u, int v); void tarjan(int u, int p); int main() { while(scanf("%d %d", &n, &m) != EOF) { memset(head, -1, sizeof(head)); memset(dfn, -1, sizeof(dfn)); memset(degree, 0, sizeof(degree)); e = 0; index = 0; num = 0; int u, v; for(int i = 0; i < m; i++) { scanf("%d %d", &u, &v); u--; v--; addEdge(u, v); } tarjan(0, -1); for(int i = 0; i < n; i++) { for(int k = head[i]; k != -1; k = edge[k].next) { if(low[i] != low[edge[k].v]) degree[low[i]]++; } } int cnt = 0; for(int i = 0; i < index; i++) { if(degree[i] == 1) cnt++; } printf("%d\n", (cnt + 1) / 2); } return 0; } void addEdge(int u, int v) { edge[e].v = v; edge[e].next = head[u]; head[u] = e++; edge[e].v = u; edge[e].next = head[v]; head[v] = e++; } void tarjan(int u, int p) { dfn[u] = low[u] = index++; for(int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].v; if(dfn[v] == -1) { tarjan(v, u); low[u] = min(low[u], low[v]); } else if(v != p) low[u] = min(low[u], dfn[v]); } }