main.cpp

强联通的两个实现。有比较好的可读性。且多次时间证明可行

#include<stdio.h>
#include<string.h>
#define  MAX 1000
struct Node{
	int x;
	Node *next;
	Node(){x=0;next=0;}
};
Node *f[MAX],*f2[MAX];
int n,k,ans;
int visit[MAX],rec[MAX],root[MAX];
void init(){
	int a,b;
	Node *temp;
	scanf("%d%d",&n,&k);
	for(int i=0;i<k;i++){
		scanf("%d%d",&a,&b);
		temp=new Node();
		temp->x=b;temp->next=f[a];f[a]=temp;
		temp=new Node();
		temp->x=a;temp->next=f2[b];f2[b]=temp;
	}
}
void dfs(int x){
	visit[x]=1;
	Node *temp=f2[x];
	while (temp){
		if (!visit[temp->x]) dfs(temp->x);
		temp=temp->next;
	}
	rec[++rec[0]]=x;
}
void dfs_(int x,int num){
	visit[x]=1;root[x]=num;
	Node *temp=f[x];
	while (temp){
		if (!visit[temp->x]) dfs_(temp->x,num);
		temp=temp->next;
	}
}
int main(){
	freopen("in.txt","r",stdin);
	init();
	memset(visit,0,sizeof(visit));
	for (int i=1;i<=n;i++)
		if (!visit[i]) dfs(i);
	memset(visit,0,sizeof(visit));ans=0;
	for (int i=n;i>=1;i--)
		if (!visit[rec[i]])
		{
			dfs_(rec[i],ans++);
		}
	for (int i=1;i<=n;i++) printf("%d ",root[i]);
	return 0;
}