P2835 刻录光盘 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int p[N],s[N];
int num[N][N];

int find(int x){  //找到x的根并实现路径压缩
	if(p[x]!=x) return p[x]=find(p[x]);
	return p[x];
}

int main(){
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++) p[i]=i;
	for(int i=1;i<=n;i++){
		int x;
		while(cin>>x,x){
			num[i][x]=1;
		}
	}
	for(int k=1;k<=n;k++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				num[i][j]=num[i][j]|(num[i][k]&&num[k][j]);
                //从i到j的距离=从i到j的距离|(从i到k的距离&从k到j的距离)
			}
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(num[i][j]){
				int pa=find(i);//因为是单向最短路,且j是新加进来的,所以不能求j的祖节点是谁,而是要把i作为j的祖节点,这样才实现了i能传向j,但j无法传向i
				p[j]=pa;
			}
		}
	}
	for(int i=1;i<=n;i++){//找到所有祖节点
		s[find(i)] =1;
	}
	int cnt=0;
	for(int i=1;i<=n;i++){
		if(s[i]) cnt++;
	}
	printf("%d\n",cnt);
	
	return 0 - 0;
}