Pagini recente » Cod sursa (job #644791) | Statistici Vlad Andrei (andutu1270) | Cod sursa (job #2009808) | Cod sursa (job #1648856) | Cod sursa (job #485749)
Cod sursa(job #485749)
#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;
}
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;
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 = 0;i < n;i++)
v[i] = 0;
for(i = 1;i <= n;i++)
if(v[i] == 0){
dfs2(i,&b[l],v);
l++;
}
int p;
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;
}