Cod sursa(job #1605114)

Utilizator Dan_RadulescuRadulescu Dan Dan_Radulescu Data 18 februarie 2016 19:32:49
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include<stdio.h>
using namespace std;
FILE *f1=fopen("ctc.in","r");
FILE *f2=fopen("ctc.out","w");
int n,m,nr,coada[100001],v[100001],nrc,i,j;
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(){
    int i,a,b;
    fscanf(f1,"%d%d",&n,&m);
    for (i=1;i<=n;i++){
        L1[i]=0;L2[i]=0;
    }
    for (i=1;i<=m;i++){
        fscanf(f1,"%d%d",&a,&b);
        adaugaresf(b,L1[a]);
        adaugaresf(a,L2[b]);
    }
    fclose(f1);
}
void dfs(int k){
   nod *q;
   v[k]=1;
   q=L1[k];
   while(q!=0){
      if (v[q->inf]==0) dfs(q->inf);
      q=q->urm;
   }
   nr++;
   coada[nr]=k;
}
void dfs2(int k,int nrc){
   nod *q;
   v[k]=nrc;
   q=L2[k];
   while(q!=0){
      if (v[q->inf]==0) dfs2(q->inf,nrc);
      q=q->urm;
   }
}
int main(){
   citire();
   for (i=1;i<=n;i++)
        if (v[i]==0) dfs(i);
   for (i=1;i<=n;i++)
    v[i]=0;
   for (i=n;i>=1;i--)
   if (v[coada[i]]==0){
    nrc++;
    dfs2(coada[i],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;
}