main2.cpp

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

#include<stdio.h>
#include<string.h>
#define  MAX 1000
struct Node{
	int x;
	Node *next;
	Node(){x=0;next=0;}
};
Node *f[MAX];
int n,k;
int visit[MAX],arv[MAX],low[MAX],root[MAX],stk[MAX];
int stp,timer;
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;
	}
}
void tarjan(int u){
	arv[u]=low[u]=timer++;
	stk[stp++]=u;visit[u]++;
	Node *temp=f[u];
	while (temp){
		if (!visit[temp->x]){
			tarjan(temp->x);
			if (low[temp->x]<low[u]) low[u]=low[temp->x];
		}else if (visit[temp->x]==1&&arv[temp->x]<low[u]){
			low[u]=arv[temp->x];
		}
		temp=temp->next;
	}
	if (low[u]==arv[u]){
		do {
			root[stk[--stp]]=u;
			visit[stk[stp]]++;
		}while (stk[stp]!=u);
	}
}
int main(){
	freopen("in.txt","r",stdin);
	init();
	for (int i=1;i<=n;i++) 
		if (!visit[i]) tarjan(i);
	for (int i=1;i<=n;i++) printf("%d ",root[i]);
	return 0;
}