36分水题求助
查看原帖
36分水题求助
246979
SalomeJLQ楼主2020/9/12 11:42

36分,四个AC,五个RE,2个WA,查不出错误,求助

#include<bits/stdc++.h>
using namespace std;
int n,head[10005],cnt,col,Dfn,top=1,k,ans1,ans2,stack_[10005],color[10005],dfn[10005],low[10005],vis[10005],in[10005],out[10005],s_e[1000005][3];
struct node{int to,next;}edge[1000005];
void build(int x,int y){
	cnt++;
	edge[cnt].to=y;
	edge[cnt].next=head[x];
	head[x]=cnt;
}
void tarjan(int u){
	Dfn++,top++;
	dfn[u]=low[u]=Dfn;
	stack_[top]=u;
	for(int i=head[u];i!=0;i=edge[i].next){
		int v=edge[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(dfn[u]==low[u]){
		col++;
		do{
			top--;
			color[stack_[top]]=col;
			vis[stack_[top]]=-1;
		}while(stack_[top]!=u);
	}
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		int x;cin>>x;
		while(x){
			build(i,x);k++;
			s_e[k][1]=i;s_e[k][2]=x;
			cin>>x;
		}
	}
	for(int i=1;i<=n;i++)
		if(!vis[i])tarjan(i);
	for(int i=1;i<=k;i++){
		int u=s_e[i][1],v=s_e[i][2];
		if(color[u]!=color[v]){
			out[color[u]]++;
			in[color[v]]++;
		}
	}
	for(int i=1;i<=col;i++){
		if(!in[i])ans1++;
		if(!out[i])ans2++;
	}
	if(col==1)cout<<1<<endl<<0;
	else cout<<ans1<<endl<<max(ans1,ans2);
	return 0;
}
2020/9/12 11:42
加载中...