【模板】tarjan求边双联通分量

#include
using namespace std;
const int z = 4096+1024;
int n, m, od[z], ans;
int use = -1, _ = 0;

struct line{
	int t, next;
} edge[z<<2];
int cnt = 1, head[z];
//cnt从1开始，为了使相同的边的i抑或1后相等；
//之所以放弃cnt从0开始，修改adedge函数，
//是因为之后循环前向星会出大问题；
void adedge(int &f,int &t) {
	edge[++cnt].next = head[f];
	edge[cnt].t = t;
	head[f] = cnt;
	return;
}

stack stk;//栈；
vector ebc[z];//存每一个边双联通分量；
bool cut[z];//边是否为桥；
int dfn[z], low[z], ti;
int belong[z];//判断某点在哪一个分量里；
void tarjan(int &u,int &pid) {
	dfn[u] = low[u] = ++ti;
	stk.push(u);
	for(int i = head[u];i;i = edge[i].next) {
		if(i == (pid^1)) continue;//WARNING！加括号！
		if(!dfn[edge[i].t]) {
			tarjan(edge[i].t,i);//顺便这里判的一直是边的id；
			low[u] = min(low[u],low[edge[i].t]);
		} else {
			low[u] = min(low[u],dfn[edge[i].t]);
		}
	}
	if(dfn[u] == low[u]) {//发现有桥，开始找分量；
		cut[pid] = true;
		++belong[0];
		int tmp;
		do {
			tmp = stk.top();
			stk.pop();
			belong[tmp] = belong[0];
			ebc[belong[0]].push_back(tmp);
		} while(tmp != u);
	}
	return;
}

int main() {
	scanf("%d %d",&n,&m);
	for(int i = 1;i <= m;++i) {
		int s, e;
		scanf("%d %d",&s,&e);
		adedge(s,e);
		adedge(e,s);
	}
	for(int i = 1;i <= n;++i) 
		if(!dfn[i]) tarjan(i,use);
	for(int u = 1;u <= n;++u) 
		for(int i = head[u];i;i = edge[i].next) 
			if(belong[u] != belong[edge[i].t]) 
				++od[belong[u]];//找每个分量的度；
	for(int i = 1;i <= belong[0];++i) 
		if(od[i] == 1) ++ans;//找缩点后的叶节点个数；
	printf("%d",(ans+1)/2);
	return 0^_^0;//^_^；
}