Cod sursa(job #1113818)

Utilizator lucamateiLuca Matei lucamatei Data 20 februarie 2014 22:18:47
Problema Componente tare conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include <fstream>


using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");

long int i,j,m,n,x,y,k;
int a[20000][20000];
int suc[10000],viz[10000];
int pred[10000],comb[10000],nr;
void mm(int v[10000])
{int i;
    for(i=1;i<=n;i++) v[i]=0;
}
void succesor(int nod)
{int i;
viz[nod]=1;suc[nod]=1;
for(i=1;i<=n;i++)
    if(a[nod][i]==1 && viz[i]==0) {succesor(i);
k++;}

}
void predecesor(int nod)
{int i;
viz[nod]=1;pred[nod]=1;
for(i=1;i<=n;i++)
    if(a[i][nod]==1 && viz[i]==0){ predecesor(i);
k++;}
}
void combin(int suc[100],int pred[100],int comb[100])
{int i,j;
nr++;
for(i=1;i<=n;i++)
    if(suc[i]==1 && pred[i]==1&&comb[i]==0)        comb[i]=nr;;


}
void afis(int comb[100])
{int i,j;
g<<nr<<endl;

for(i=1;i<=nr;i++)
{
for(j=1;j<=n;j++)
    if(comb[j]==i)g<<j<<' ';
g<<endl;
}
}

int main()
{int i;
f>>n>>m;
for(i=1;i<=m;i++)
    {f>>x>>y; a[x][y]=1;}
for(i=1;i<=n;i++)
{k=0;
   mm(viz);
   mm(suc);
   mm(pred);
   if(comb[i]==0)
    {succesor(i);
     mm(viz);
     predecesor(i);
    if(k) combin(suc,pred,comb);
   }
}
   afis(comb);

f.close();
g.close();
}