92pts求调
查看原帖
92pts求调
1287549
l1754002917楼主2024/11/4 20:16
#include<bits/stdc++.h>
using namespace std;
int n,m;
vector<int>v[10005];
stack<int>stk;
int dfn[10005],low[10005],co[10005],cnt[10005];
int tot,col;
inline int read(){
	int s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-')w=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		s=s*10+ch-48;
		ch=getchar();
	}
	return s*w;
}
void tarjan(int x){
	dfn[x]=low[x]=++tot;
	stk.push(x);
	int l=v[x].size();
	for(int i=0;i<l;i++){
		int y=v[x][i];
		if(!dfn[y]){
			tarjan(y);
			low[x]=min(low[x],low[y]);
		}
		else if(!co[y]){
			low[x]=min(low[x],dfn[y]);
		}
	}
	if(dfn[x]==low[x]){
		co[x]=++col;
		cnt[col]=1;
		while(!stk.empty()&&stk.top()!=x){
			int y=stk.top();
			stk.pop();
			co[y]=col;
			cnt[col]++;
		}
		stk.pop();
	}
}
int main(){
//	freopen("1.in","r",stdin);
//	freopen("1.out","w",stdout);
	n=read();
	m=read();
	for(int i=1;i<=m;i++){
		int x,y;
		if(x==y)continue;
		x=read();
		y=read();
		v[x].push_back(y);
	} 
	for(int i=1;i<=n;i++){
		if(!dfn[i]){
			tarjan(i);
		}
	}
	int p=0;
	for(int i=1;i<=col;i++){
		if(cnt[i]>1)p++;
	}
	printf("%d\n",p);
	return 0;
}
2024/11/4 20:16
加载中...