54分蒟蒻求助
查看原帖
54分蒟蒻求助
391830
Locked_Fog楼主2021/11/27 08:29

同样的代码过得了P2812 校园网络【[USACO]Network of Schools加强版】却过不了这道题???

#include<bits/stdc++.h>
using namespace std;

const int maxn=1e7,maxm=1e7;
int len,head[maxn];
struct Edge{int from,to,next;}e[maxm];
void insert(int u,int v){
	e[++len].from=u;e[len].to=v;e[len].next=head[u];head[u]=len;
}

int dfn[maxn],low[maxn],tim,vis[maxn],scc,belong[maxn];//1->gray  0->white  -1->black
stack<int>q;

void Tarjan(int u){
	q.push(u);vis[u]=1;low[u]=dfn[u]=++tim;
	for(int i=head[u];i;i=e[i].next){
		int v=e[i].to;
		if(vis[v]==0){
			Tarjan(v);
			low[u]=min(low[u],low[v]);
		}else if(vis[v]==1){
			low[u]=min(low[u],dfn[v]);
		}
	}
	
	if(low[u]==dfn[u]){
		scc++;
		int v=q.top();
		while(dfn[v]!=low[v]){
			belong[v]=scc;
			q.pop();
			v=q.top();
		}
		q.pop();
		belong[v]=scc;
	}
}

int n,ind[maxn],oud[maxn];

void Read(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		while(true){
			int v;
			scanf("%d",&v);
			if(v==0)break;
			insert(i,v);
		}
	}
}
void Solve(){
	int ans=0;
	for(int i=1;i<=n;i++){
		if(vis[i]==0)Tarjan(i);
	}
	for(int i = 1;i<=len;i++){
		if(belong[e[i].to]!=belong[e[i].from]){
			// printf("Edge: from %d to %d\n",e[i].from,e[i].to);
			oud[belong[e[i].from]]++;
			ind[belong[e[i].to]]++;
		}
	}
	for(int i=1;i<=scc;i++){
		if(ind[i]==0)ans++;
	}
	
	printf("%d\n",ans);
	int ans1 = 0;

	for(int i=1;i<=scc;i++){
		if(oud[i]==0)ans1++;
	}
	if(scc==1){ans=0;ans1=0;}
	printf("%d",max(ans,ans1));

	
}
int main(){
	Read();
	Solve();
	return 0;
}

求大佬帮忙看看

2021/11/27 08:29
加载中...