Cod sursa(job #1603477)

Utilizator Dan_RadulescuRadulescu Dan Dan_Radulescu Data 17 februarie 2016 16:31:31
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 kb
#include<stdio.h>
using namespace std;
FILE *f1=fopen("ctc.in","r");
FILE *f2=fopen("ctc.out","w");
int n,m,v[100001],ordine[100001],timp[100001],i,nrc,k,j,ti;
struct nod{
   int inf;
   nod *urm;
}*L1[100001],*L2[100001];
void adaugaresf(int val,nod *&vf){
    nod *q;
    q=new nod;
    q->inf=val;
    q->urm=vf;
    vf=q;
}
void citire(){
   fscanf(f1,"%d%d",&n,&m);
   int k,a,b;
   for (k=1;k<=n;k++){
     L1[k]=0;
     L2[k]=0;
   }
   for (k=1;k<=m;k++){
       fscanf(f1,"%d%d",&a,&b);
       adaugaresf(b,L1[a]);
       adaugaresf(a,L2[b]);
   }
   fclose(f1);
}
void dfs(int k,int nr){
    v[k]=nr;
    nod *q;
    q=L2[k];
    while(q!=0){
        if (v[q->inf]==0) dfs(q->inf,nr);
        q=q->urm;
    }
}
void dfs_timp(int k){
    nod *q;
    q=L1[k];
    v[k]=1;
    while(q!=0){
        if (v[q->inf]==0){
            dfs_timp(q->inf);
        }
        q=q->urm;
    }
    ti++;
    timp[ti]=k;
}
int main(){
   citire();ti=1;
   for (i=1;i<=n;i++){
    if (v[i]==0){
     dfs_timp(i);
    }
   }
   for (i=1;i<=n;i++)
        v[i]=0;
   for (i=ti;i>=1;i--){
      k=timp[i];
      if (v[k]==0) {
        nrc++;
        dfs(k,nrc);
      }
   }
   nrc--;
   fprintf(f2,"%d\n",nrc);
   for (i=1;i<=nrc;i++){
      for (j=1;j<=n;j++)
        if (v[j]==i) fprintf(f2,"%d ",j);
      fprintf(f2,"\n");
   }
   fclose(f2);
   return 0;
}