WA#11#12,求调玄关
查看原帖
WA#11#12,求调玄关
941580
ilmex楼主2024/9/11 19:24
#include<bits/stdc++.h>
using namespace std;
const int N=100001;
int n,m,x,y,d[N],l[N],b[N],w,c,r;
bool f[N];
vector<int>g[N],s[N];
stack<int>q;
void tj(int u){
	d[u]=l[u]=++w;
	q.push(u);f[u]=1;
	for(int i=0; i<g[u].size(); i++){
		int v=g[u][i];
		if(!d[v]){
			tj(v);
			l[u]=min(l[u],l[v]);
		}
		else if(f[v])l[u]=min(l[u],d[v]);
	}
	if(d[u]==l[u]){
		c++;int v;
		do{
			v=q.top();q.pop();
			s[c].push_back(v);b[v]=c;
		}while(v!=u);
	}
}
int main(){
	scanf("%d%d", &n, &m);
	while(m--){
		scanf("%d%d", &x, &y);
		g[x].push_back(y);
	}
	for(int i=1; i<=n; i++){
		if(!d[i])tj(i);
	}
	for(int i=1; i<=n; i++){
		if(s[i].size()>1){
			r++;
		}
	}
	printf("%d", r);
	return 0;
}
2024/9/11 19:24
加载中...