burning bridges(割边，有平行边).cpp

杭电acm解题报告2001---2099.

#include <cstdio>
#include <string>
#include <vector>
#include <sstream>
#include <algorithm>
using namespace std;

const int MAX = 11000;
int n,m;
vector< pair<int,int> > path[MAX];
int vis[MAX], low[MAX];
vector<int> cutpoint;
vector<int> bridge;

#define mclear(x) memset((x), 0, sizeof((x)))

void dfs(int pos, int deep, int father) {
	int i,j, total = 0;
	bool cut = false;
	int reback = 0;
	vis[pos] = deep;
	low[pos] = deep;
	int ls = path[pos].size();
	for(j=0;j<ls;j++) {
		i = path[pos][j].first;
		if(i == father) reback ++;
		if(vis[i] == 0) {
			dfs(i, deep+1, pos);
			total ++;
			low[pos] = min(low[i], low[pos]);
			if((deep == 1 && total > 1) || 
				(deep != 1 && low[i] >= vis[pos])) cut = true;
			if(low[i] > vis[pos]) bridge.push_back(path[pos][j].second);
		}
		else if(i != father) {
			low[pos] = min(vis[i], low[pos]);
		}
	}
	if(reback > 1) low[pos] = min(low[pos], vis[father]);
	if(cut) cutpoint.push_back(pos);
}

void find_cut() {
	int i;
	mclear(vis); mclear(low);
	cutpoint.clear(); bridge.clear();
	for(i=1;i<=n;i++) {
		if(vis[i] == 0) {
			dfs(i, 1, i);
		}
	}
}

int main() {
	int i,t;
	scanf("%d", &t);
	while(t --) {
		scanf("%d %d", &n,&m);
		for(i=0;i<=n;i++) path[i].clear();
		for(i=1; i<=m ;i++) {
			int x,y;
			scanf("%d %d", &x,&y);
			path[x].push_back( pair<int,int>(y,i) );
			path[y].push_back( pair<int,int>(x,i) );
		}
		find_cut();
		printf("%d\n", bridge.size());
		sort(bridge.begin(), bridge.end());
		for(i=0;i<bridge.size();i++) {
			if(i > 0) putchar(' ');
			printf("%d", bridge[i]);
		}
		if(bridge.size() > 0) printf("\n");
		if(t != 0) printf("\n");
	}
}