Cod sursa(job #1605136)

Utilizator Dan_RadulescuRadulescu Dan Dan_Radulescu Data 18 februarie 2016 19:47:17
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.5 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 inf2;
   nod *urm2;
}*L1[100001],*L2[100001];
struct cod{
   int inf;
   cod *urm;
}*sol[100001];
void adaugaresf(int val,nod *&vf){
    nod *q;
    q=new nod;
    q->inf2=val;
    q->urm2=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->inf2]==0) dfs(q->inf2);
      q=q->urm2;
   }
   nr++;
   coada[nr]=k;
}
void dfs2(int k,int nrc){
   nod *q;
   cod *w;
   v[k]=nrc;
   q=L2[k];
   w=new cod;
   w->inf=k;
   w->urm=sol[nrc];
   sol[nrc]=w;
   while(q!=0){
      if (v[q->inf2]==0) dfs2(q->inf2,nrc);
      q=q->urm2;
   }
}
int main(){
   citire();
   for (i=1;i<=n;i++)
    sol[i]=0;
   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);
   cod *w;
   for (i=1;i<=nrc;i++){
       w=sol[i];
       while(w!=0){
         fprintf(f2,"%d ",w->inf);
         w=w->urm;
       }
       fprintf(f2,"\n");
   }
   fclose(f2);
   return 0;
}