球球大佬,85pts看不到错在哪,和题解一样
查看原帖
球球大佬,85pts看不到错在哪,和题解一样
808332
BVVD_FM楼主2023/10/4 19:54
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10,M=5e5+10;
int head[N],nxt[M],ver[N],idx;
int s[N],top,dfn[N],low[N],times,vis[N];
int id[N],scnt;
int biaoji[N]; 
int n,m,x,y;
inline void add(int x,int y){
	ver[++idx]=y;
	nxt[idx]=head[x];
	head[x]=idx;
}
inline int read(){
    int op = 1, x = 0; 
	char ch = getchar();while(!isdigit(ch)) {if(ch == '-')   op = -1;ch = getchar();}
	while(isdigit(ch)) {x = (x << 3) + (x << 1) + ch - '0';ch = getchar();}
    return op * x;
}
void dfs(int u){
	dfn[u]=low[u]=++times;
	vis[u]=1;
	s[++top]=u;
	for(int i=head[u];~i;i=nxt[i]){
		int v=ver[i];
		if(!dfn[v]){
			dfs(v);
			low[u]=min(low[u],low[v]);
		}else if(vis[v]){
			low[u]=min(low[u],dfn[v]);
		}
	}
	if(dfn[u]==low[u]){
		scnt++;
		do{
			vis[s[top]]=0;
			id[s[top]]=scnt;
		}while(u!=s[top--]);
	}
}
void tarjan(){
	for(int i=1;i<=n;i++){
		if(!dfn[i])dfs(i); 
	} 
}
int main(){
	n=read(),m=read();
	memset(head,-1,sizeof head);
	for(int i=1;i<=m;i++){
		x=read(),y=read();
		add(x,y);
	}
	tarjan();
	for(int u=1;u<=n;u++){
		for(int i=head[u];~i;i=nxt[i]){
			int v=ver[i];
			if(id[v]!=id[u]){//标记此连通块
				biaoji[id[v]]=1;	
			}
		}
	}
	int ans=0;
	for(int i=1;i<=scnt;i++){
		if(!biaoji[i])ans++;
	}
	cout<<ans;
	return 0;
}//farl
2023/10/4 19:54
加载中...