Cod sursa(job #485972)

Utilizator edward_alexStanciu Alexandru Marian edward_alex Data 20 septembrie 2010 10:28:56
Problema Componente tare conexe Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 1.87 kb
#include<stdio.h>
#include<stdlib.h>

typedef struct nod{
    int info;
    struct nod *next;
}nod;

nod *a[1000009];
nod *c[1000009];
nod *b[1000009];

void adauga(int x,nod **u){
    nod *nou = (nod*)malloc(sizeof(nod));
    nod *ultim = *u;
    nou->info = x;
    nou->next = ultim;
    *u = nou;
}

int sterge(nod **u){
    nod *q = *u;
    int x = q->info;
    *u = (*u)->next;
    free(q);
    return x;
}

void free_stiva(nod *u){
    nod *aux;
    while(u != NULL){
	aux = u;
	u = u->next;
	free(aux);
    }
}

void dfs1(int x,int *v,nod **u){
    int y;
    v[x] = 1;
    nod *q;
    for(q = a[x];q != NULL;q = q->next){
	y = q->info;
	if(v[y] == 0)
	    dfs1(y,v,u);
    }
    adauga(x,u);
}

void dfs2(int x,nod **u,int *v){
    int y;
    v[x] = 1;
    adauga(x,u);
    nod *q;
    for(q = c[x];q != NULL;q = q->next){
	y = q->info;
	if(v[y] == 0){
	    dfs2(y,u,v);
	}
    }
}

int main(){
    FILE *f,*g;
    f = fopen("ctc.in","r");
    g = fopen("ctc.out","w");
    int n,m,i,k1,k2;
    int p;
    fscanf(f,"%d%d",&n,&m);
    for(i = 0;i < n;i++)
	a[i] = NULL;
    for(i = 0;i < n;i++)
	b[i] = NULL;
    for(i = 0;i < n;i++)
	c[i] = NULL;
    for(i = 0;i < m;i++){
	fscanf(f,"%d%d",&k1,&k2);
	adauga(k2,&a[k1]);
	adauga(k1,&c[k2]);
    }
    int *v = (int*)calloc((n + 1),sizeof(int));
    nod *u = NULL;
    int l = 0;
    for(i = 1;i <= n;i++)
	if(v[i] == 0)
	    dfs1(i,v,&u);
    for(i = 1;i <= n;i++)
	v[i] = 0;
    while(u != NULL){
	p = sterge(&u);
	if(v[p] == 0){
	    dfs2(p,&b[l],v);
	    l++;
	}
    }
    fprintf(g,"%d\n",l);
    for(i = 0;i  < l;i++){
	nod *h;
	for(h = b[i]; h != NULL;h = h->next){
	    p = h->info;
	    fprintf(g,"%d ",p);
	}
	fprintf(g,"\n");
    }
    free(v);
    free_stiva(u);
    for(i = 1;i <= n;i++)
	free_stiva(a[i]);
    for(i = 0;i < l;i++)
	free_stiva(b[i]);
    for(i = 1;i <= n;i++)
	free_stiva(c[i]);
    fclose(f);
    fclose(g);
    return 0;
}