【模板】Tarjan求桥（无向图）

#include
#include
#include
#include
 
namespace bikuhiku {
    template  _T gtr(_T &_compare_x,_T &_compare_y) {
        return _compare_x > _compare_y ? _compare_x : _compare_y;
    }
    template  _T les(_T &_compare_x,_T &_compare_y) {
        return _compare_x < _compare_y ? _compare_x : _compare_y;
    }
    template  void get_int(_T &_data_x) {
        int _signal = 1;
        char _get_c;
        _data_x = 0;
        for(_get_c = getchar();_get_c < '0'||_get_c > '9';_get_c = getchar()) if(_get_c == '-') _signal = -1;
        for(;_get_c >= '0'&&_get_c <= '9';_get_c = getchar()) _data_x = (_data_x<<3)+(_data_x<<1)+(_get_c^48);
        _data_x *= _signal;
        return;
    }
    template  void put_int(_T _data_x) {
        if(_data_x > 9) put_int(_data_x/10);
        putchar((_data_x%10)^48);
        return;
    }
    int _ = 0;
    int _aUse = 1;
    int _rUse = -1;
}//定义一块命名空间；
using namespace bikuhiku;
using namespace std;

const int z = 32768;
int n, m;
int s, e;

struct line{
	int t, next;
} edge[z<<1];//注意开双边；
int cnt, head[z];
void adedge(int &f,int &t) {
	edge[++cnt].next = head[f];
	edge[cnt].t = t;
	head[f] = cnt;
	return;
}

stack stk;
int dfn[z], low[z], time;
int tot;
void tarjan(int &u,int &p) {
	dfn[u] = low[u] = ++time;
	bool fst = false;
	for(int i = head[u];i;i = edge[i].next) {
		if(!fst&&edge[i].t == p) {
			fst = true;
			continue;
		}
		if(!dfn[edge[i].t]) {
			tarjan(edge[i].t,u);
			low[u] = les(low[u],low[edge[i].t]);
			if(dfn[u] < low[edge[i].t]) ++tot;
		} else {
			low[u] = les(low[u],dfn[edge[i].t]);
		}
	}
	return;
}

void init() {
	cnt = tot = time = 0;
	memset(dfn,0,sizeof(dfn));
	memset(low,0,sizeof(low));
	memset(head,0,sizeof(head));
	while(!stk.empty()) stk.pop();
}

int main() {
	while(1) {
		get_int(n);
		get_int(m);
		if(!n&&!m) break;
		init();
		for(int i = 1;i <= m;++i) {
			get_int(s);
			get_int(e);
			adedge(s,e);
			adedge(e,s);
		}
		for(int i = 1;i <= n;++i)
			if(!dfn[i]) tarjan(i,_);
		printf("%d\n",tot);
	}
	return 0^_^0;
}