一个点都没过,求助
查看原帖
一个点都没过,求助
580194
primer_z楼主2022/8/5 15:42
#include<bits/stdc++.h>
using namespace std;
#define maxn 5000005
int head[maxn],ind[maxn];
bool vis[maxn];
int cnt,sum,ans; int n,m; int t;
int In,Out;
int low[maxn],dfn[maxn],scc[maxn];
stack<int> s;
struct edge{
	int to,next,from;
}edge[5000005];
void add(int u,int v){
	edge[++cnt].to=v; edge[cnt].from=u; edge[cnt].next=head[u];
	head[u]=cnt;
}
void tj(int x){
	low[x]=dfn[x]=++t;
	vis[x]=1;
	s.push(x);
	for(int i=head[x];i;i=edge[i].next){
		int v=edge[i].to;
		if(!dfn[v]){
			tj(v);
			low[x]=min(low[x],low[v]);
		}
		else if(vis[v]){
			low[x]=min(low[x],dfn[v]);
		}
	}
	if(low[x]==dfn[x]){
		int to;
		++sum;
		while(!s.empty()){
            to=s.top();
			s.pop();
			vis[to]=0;
			scc[to]=sum;
            if(to==x) break;
			}
	}return ;
}
int main(){
	scanf("%d",&n);
	for (int i = 1; i <= n; i++) {
        int u,v;
        cin>>u>>v;
        if(u==v) continue;
        add(u,v);
        }
	for(int i=1;i<=n;i++){
		if(!dfn[i]){
			tj(i);
		}
	}
	for (int i = 1; i <= n; i++){
		for (int j = head[i]; j; j = edge[j].next){
			int v = edge[j].to;
			if (scc[i] != scc[v]){
				ind[scc[v]]++;
			}
		}
	}
	for(int i=1;i<=sum;i++){
		if(!ind[i]) In++;
	}
	cout<<In;
	return 0;
}
2022/8/5 15:42
加载中...