ZOJ 2588 Burning Bridges
题意：给定一个无向图连通图，（其中可能有重边），要求去掉一条边之后，使得整个图不再连通。输出这些符合条件的边的序号。
思路：这就是一个简单的无向图求割边，需要注意的是这个无向图有重边，重边一定不是割边。
代码：
/*=========================================
无向图求割点和桥
复杂度：O(E + V)
割点：
1：若k为深搜树的根Root，当且仅当k的儿子数（分支数）>=2时k为割点；
2：若k为搜索树的中间结点（即k既不为根也不为叶），那么k必然有father和son，若low[son]>= dfn[k]，则k必然为割点。
割桥：
如果low[v] > dfn[u] 则(u,v)为割桥 (需要判断是否有重边，如果有重边一定不是割边）
=========================================*/
/*
ID: wuqi9395@126.com
PROG:
LANG: C++
*/
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<vector>
#include<string>
#include<fstream>
#include<cstring>
#include<ctype.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define INF (1<<30)
#define PI acos(-1.0)
#define mem(a, b) memset(a, b, sizeof(a))
#define rep(i, a, n) for (int i = a; i < n; i++)
#define per(i, a, n) for (int i = n - 1; i >= a; i--)
#define eps 1e-6
#define debug puts("===============")
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define POSIN(x,y) (0 <= (x) && (x) < n && 0 <= (y) && (y) < m)
typedef long long ll;
typedef unsigned long long ULL;
const int maxn = 11000;
const int maxm = 110000;
int n, m;
struct node {
int v, id, tot;
node(int _v, int _id, int _tot) {
v = _v, id = _id, tot = _tot;
}
};
vector<node> g[maxn];
int dfn[maxn], low[maxn], vis[maxn], sub[maxn]; //sub记录每个割点分为多少块
bool cut[maxn];
int bridge[maxm], cnt;
void dfs(int u, int f, int dep) {
vis[u] = 1;
dfn[u] = low[u] = dep;
int child = 0;
for (int i = 0; i < g[u].size(); i++) if (g[u][i].v != f) {
int v = g[u][i].v;
if (vis[v] == 1 && dfn[v] < low[u]) low[u] = dfn[v]; //回边更新low值
if (vis[v] == 0) {
dfs(v, u, dep + 1);
child++;
if (low[v] < low[u]) low[u] = low[v]; //通过儿子回到祖先
if (low[v] > dfn[u] && g[u][i].tot == 1) bridge[cnt++] = g[u][i].id;
}
}
vis[u] = 2;
}
void cut_bridge() {
cnt = 0;
memset(vis, 0, sizeof(int) * (n + 10));
dfs(1, -1, 0); //i为一个点
//如果多个连通块，需要对每一个连通块调用dfs
}
int main () {
int T;
scanf("%d", &T);
while(T--) {
scanf("%d%d", &n, &m);
for (int i = 0; i <= n; i++) g[i].clear();
int u, v;
for (int i = 1; i <= m; i++) {
scanf("%d%d", &u, &v);
bool flag = false;
for (int j = 0; j < g[u].size(); j++) if (g[u][j].v == v) {
g[u][j].tot++;
flag = true;
break;
}
if (flag) for (int j = 0; j < g[v].size(); j++) if (g[v][j].v == u) {
g[v][j].tot++;
break;
}
if (!flag)
g[u].pb(node(v, i, 1)), g[v].pb(node(u, i, 1));
}
cut_bridge();
sort(bridge, bridge + cnt);
printf("%d\n", cnt);
rep(i, 0, cnt) printf("%d%c", bridge[i], i == cnt - 1 ? '\n' : ' ');
if (T > 0) puts("");
}
return 0;
}