求助大佬!WA54分 附样例三 缩点错了?
查看原帖
求助大佬!WA54分 附样例三 缩点错了?
755293
vegetable_doggy楼主2023/10/5 20:17
#include<bits/stdc++.h>
#define itn int
#define ll long long
using namespace std;
const int N=1e2+10;
int n; 
int dfn[N],low[N],id;
struct no{
	int v,net;
}e[N*N];
int h[N],cnt;
struct node{
	int v,net;
}sc[N*N];
int sch[N],scnt,son[N];
void add(int x,int y){
	cnt++;
	e[cnt].v=y;
	e[cnt].net=h[x];
	h[x]=cnt;
}
int scc[N];
stack <itn> st;
void tarjan(int u){
	low[u]=dfn[u]=++id;
	st.push(u);
	for(itn i=h[u];i;i=e[i].net ){
		int v=e[i].v;
		if(!dfn[v]){
			tarjan(v);
			low[u]=min(low[u],low[v]);
		}else if(!scc[v]){
			low[u]=min(low[u],dfn[v]);
		}
	}
	if(low[u] == dfn[u]){
		scc[u] = ++scnt;
		while(st.top() != u){
			scc[st.top()]=scnt;
			st.pop();
		}
		st.pop();
	}
}
int fa[N];
void addscc(int x,int y){
	cnt++;
	sc[cnt].v=y;
	sc[cnt].net=sch[x];
	sch[x]=cnt;
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		int x;
		while(cin>>x){
			if(!x){
				break ;
			}
			add(i,x);
		}
	}
	for(int i=1;i<=n;i++){
		if(!dfn[i]){
			tarjan(i);
		}
	}
	cnt=0;
	for(int i=1;i<=scnt;i++){
		for(itn j=h[i];j;j=e[j].net ){
			int v=e[j].v;
			if(scc[i]!=scc[v]){
			//	addscc(scc[i],scc[v]);
				fa[scc[v]]++;
				son[scc[i]]++;
			}
		}
	}
	cnt=0;
	int cnt1=0;
	if(n==1){
		cout<<1<<"\n"<<1;
		return 0;
	}
	
	for(int i=1;i<=scnt;i++){
		if(!fa[i]){
			cnt++;
		}
		if(!son[i]){
			cnt1++;
		}
	}
	cnt1=max(cnt,cnt1);
	cout<<cnt<<"\n"<<cnt1;
//	printf("%d\n%d",cnt,cnt1);
	return 0;
}//样例三 输出 64 66 正解 63 65 
//100
//0
//0
//0
//30 0
//3 0
//0
//0
//44 59 0
//0
//70 0
//0
//0
//0
//0
//87 0
//14 0
//0
//0
//0
//45 0
//0
//85 0
//0
//41 0
//15 0
//0
//11 0
//0
//23 99 0
//0
//0
//0
//0
//0
//0
//0
//0
//19 0
//0
//43 0
//19 0
//64 0
//31 72 0
//0
//0
//0
//0
//0
//24 69 0
//0
//52 100 0
//0
//0
//66 0
//0
//60 0
//0
//0
//0
//0
//0
//0
//10 97 0
//0
//0
//41 42 0
//100 0
//0
//49 98 0
//0
//32 0
//84 0
//0
//71 0
//0
//5 0
//0
//92 0
//44 0
//0
//0
//20 26 0
//0
//0
//23 0
//0
//0
//0
//0
//0
//0
//0
//0
//72 0
//0
//0
//0
2023/10/5 20:17
加载中...