95pts WA on#13求助
查看原帖
95pts WA on#13求助
739899
p256rrq楼主2024/4/18 18:15

RT

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
const int M=1e6+5;
int n,m;
int cnt,dfn[N],low[N];
int tot,col[N],in[N];
int s[N],tail;
bitset<N>ins;
int head[N],k;
struct Edge{
	int u,v;
	int nxt;
}e[M];
inline int read(){
	int res=0,sym=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') sym=-1;
		ch=getchar();
	}while(ch>='0'&&ch<='9'){
		res=(res<<3)+(res<<1)+(ch^48);
		ch=getchar();
	}return res*sym;
}
inline void add_edge(int u,int v){
	++k;
	e[k].v=v;
	e[k].u=u;
	e[k].nxt=head[u];
	head[u]=k;
}
inline void paint(int x){
	--tail;ins[x]=0;
	col[x]=tot;
}
void tarjan(int x){
	int v;
	dfn[x]=low[x]=++cnt;
	s[++tail]=x;ins[x]=1;
	for(int i=head[x];i;i=e[i].nxt){
		v=e[i].v;
		if(!dfn[v]){
			tarjan(v);
			low[x]=min(low[x],low[v]);
		}else if(ins[v]) low[x]=min(low[x],dfn[v]);
	}if(dfn[x]==low[x]){
		++tot;
		int tp=s[tail];
		while(tp!=x){
			paint(tp);
			tp=s[tail];
		}paint(x);
	}
}
int main(){
	n=read();m=read();
	int u,v;
	while(m--){
		u=read();v=read();
		add_edge(u,v);
	}
	for(int i=1;i<=n;++i)
		if(!dfn[i]) tarjan(i);
	for(int i=1;i<=k;++i){
		head[i]=0;
		u=col[e[i].u];
		v=col[e[i].v];
		if(u==v) continue;
		in[v]++;
	}
	int ans=0;
	for(int i=1;i<=tot;++i)
		if(!in[i]) ++ans;
	cout<<ans<<"\n";
	return 0;
} 
2024/4/18 18:15
加载中...