Cod sursa(job #325884)

Utilizator ciprianfFarcasanu Alexandru Ciprian ciprianf Data 22 iunie 2009 20:46:22
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include <stdio.h>
#include <stdlib.h>
#define N 100005
int *v[N],*t[N],n,m,f[N],ft[N],s1[N],s2[N],c;
void dfs(int x){
	f[x]=1;
	for(int i=1;i<=v[x][0];i++)
		if(!f[v[x][i]])
			dfs(v[x][i]);
	s1[++s1[0]]=x;
}
void dfs2(int x){
	ft[x]=1;
	for(int i=1;i<=t[x][0];i++)
		if(!ft[t[x][i]])
			dfs2(t[x][i]);
	s2[++s2[0]]=x;
}
void solve(){
	int i;
	for(i=1;i<=n;i++)
		if(!f[i])
			dfs(i);
	for(i=n;i;i--)
		if(!ft[s1[i]]){
			c++;
			dfs2(s1[i]);
			s2[0]++;
		}
	printf("%d\n",c);
	for(i=1;i<=s2[0];i++)
		if(s2[i])
			printf("%d ",s2[i]);
		else printf("\n");
}
int main(){
	int i,x,y;
	freopen("ctc.in","r",stdin);
	freopen("ctc.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++){
		//scanf("%d%d",&x,&y);
		v[i]=(int*)malloc(4);
		t[i]=(int*)malloc(4);
		v[i][0]=t[i][0]=0;
	}
	for(i=1;i<=m;i++){
		scanf("%d%d",&x,&y);
		v[x][0]++;
		v[x]=(int*)realloc(v[x], (v[x][0]+1)*4); v[x][v[x][0]]=y;
		t[y][0]++;
		t[y]=(int*)realloc(t[y], (t[y][0]+1)*4); t[y][t[y][0]]=x;
	}
	solve();
	return 0;
}