84分求助
查看原帖
84分求助
250097
BaYueXiang楼主2022/10/9 17:09
#include<bits/stdc++.h>
using namespace std;
int n,m,h[10001],color[10001],dfn[10001],low[10001],lin,cnt; 
bool book[10001];
stack<int> q;
struct node {
	int v,next;
}edge[100001];
void ae (int a,int u,int v) {
	edge[a].v=v;
	edge[a].next=h[u];
	h[u]=a;
}
void tarjan (int x) {
	dfn[x]=low[x]=++lin;
	q.push(x);
	book[x]=true;
	for (int a=h[x];a;a=edge[a].next) {
		int v=edge[a].v;
		if (dfn[v]) low[x]=min(low[x],dfn[v]);
		else {
			tarjan(v);
			low[x]=min(low[v],dfn[v]);
		}
	}
	if (dfn[x]==low[x]) {
		cnt++;
		int tmp;
		if (q.size()==1) cnt--;
		else {
		    while (!q.empty()) {
    			tmp=q.top();
    			color[tmp]=cnt;
    			q.pop();
    		}
		}
    		
	}
}
int main () {
	cin >>n>>m;
	for (int a=1;a<=m;a++) {
		int u,v;
		cin >>u>>v;
		ae((a<<1)-1,u,v);
		ae(a<<1,v,u);
	}
	for (int a=1;a<=n;a++) 
		if (!color[a] && !book[a]) {
			while (!q.empty()) q.pop();
			tarjan(a);
		}
	cout <<cnt;
	return 0;
}
2022/10/9 17:09
加载中...