桥.cpp

本人参加ACM竞赛使用的一些算法模板

/******************************************************************
*
*   求桥的算法  (zoj 2588	Burning Bridges)
*
*******************************************************************/

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <set>
using namespace std;
int N, M;
int const MAXN = 204800;
struct node{//边节点
	int u, v, num;//num是桥的标号
	node(){}
	node(int u_, int v_){
		u = u_;
		v = v_;
	}
};
node edge[MAXN];
struct cmp{
	bool operator() (node a, node b){
		if(a.u != b.u){
			return a.u < b.u;
		}
		return a.v < b.v;
	}
};
void read_data(){
	scanf("%d %d", &N, &M);
	for (int i = 0; i < M; ++i){
		scanf("%d %d", &edge[i].u, &edge[i].v);
		--edge[i].u;
		--edge[i].v;
		edge[i].num = i + 1;
		edge[i + M] = edge[i];
		swap(edge[i + M].u, edge[i + M].v);
	}
	M *= 2;
	sort (edge, edge + M, cmp() );
}
int T, root;
int Anc[MAXN];//记录祖先节点
int D[MAXN], C[MAXN], A[MAXN];//辅助数组
set <int> bridge;//记录桥的set
void init(){//注意初始化
    for(int  i = 0; i < N; i++)
        C[i] = 0;
    T = 0;
	root = 0;
	bridge.clear();
}
void DFS(int k, int father, int deep){
	//调用与求割顶算法类似，初次调用的时候，取k=0(若点从0开始标记）作为当前点，
	//father为-1，depp为0。
	int i, tot(0);
	C[k] = 1;
	D[k] = deep;
	Anc[k] = deep;
	int op = lower_bound(edge, edge + M, node(k, -1), cmp() ) - edge;
	for (int j = op; j < M && edge[j].u == k; ++j){
		i = edge[j].v;
		if(i != father && C[i] == 1){
			Anc[k] = min(Anc[k], D[i]);
		}
		if(C[i] == 0){
			DFS(i, k, deep + 1);
			++tot;
			Anc[k] = min(Anc[k], Anc[i]);
			if(Anc[i] > D[k]){//i点在k之前，找到桥，插入集合中
				if(j < M - 1 && edge[j].u == edge[j + 1].u &&
				    edge[j].v == edge[j + 1].v)
				    {//原题中有重边
					}
					else{
						bridge.insert(edge[j].num);
					}
			}
		}
	}
	C[k] = 2;
	A[i] = ++T;
}
int main(){
	int T;
	scanf("%d", &T);
	bool flag(false);
	while (T--){
		read_data();
		init();
		DFS(0, -1, 0);
		if(flag){
			printf("\n");
		}
		flag = true;
		printf("%d\n", bridge.size() );
		bool f(false);
		for (set <int>::iterator iter = bridge.begin();
		    iter != bridge.end(); ++iter){
				if(f){
					printf(" ");
				}
				f = true;
				printf("%d", *iter);
			}
		if(bridge.size() ){
			printf("\n");
		}
	}
	return 0;
}