1
2
3
4
5
6
7
8
9
10
11
12
void tarjan(int u,int eid) {
	dfn[u]=low[u]=++indx;
	stk[++tp]=u;
	for(int i=head[u]; ~i; i=edge[i].nxt) {
		int v=edge[i].to;
		if(dfn[v]==0) {
			tarjan(v,i);
			low[u]=min(low[u],low[v]);
		}
		if(i!=(eid^1)) low[u]=min(low[u],dfn[v]);
	}
}

A. 桥（割边）

- 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
const int N=3e4+10;
int n,m,a,b;
vector<pair<int,int> >g[N];
int dfn[N],low[N],cnt,ans;
void DFS(int u,int bef){
	dfn[u]=low[u]=++cnt;
	for(int i=0;i<g[u].size();++i){
		int v=g[u][i].first,id=g[u][i].second;
		if(dfn[v]==0){
			DFS(v,id);
			low[u]=min(low[u],low[v]);
			if(low[v]>dfn[u])
				++ans;
		}
		else if(bef!=id)
			low[u]=min(low[u],dfn[v]);
		
	}
}
signed main(){
	while(scanf("%d%d",&n,&m)!=EOF&&n!=0&&m!=0){
		memset(dfn,0,sizeof dfn);
		memset(low,0,sizeof low);
		for(int i=1;i<=n;++i)
			g[i].clear();
		ans=cnt=0;
		for(int i=1;i<=m;++i){
			scanf("%d%d",&a,&b);
			g[a].push_back(make_pair(b,i));
			g[b].push_back(make_pair(a,i));
		}
		for(int i=1;i<=n;++i)
			if(!dfn[i])
				DFS(i,0);
		printf("%d\n",ans);
	}
	return 0;
}

缩点这套不是很会，等补题吧