Cod sursa(job #2257990)

Utilizator petrinamazarianuMazarianu Petrina petrinamazarianu Data 10 octombrie 2018 18:28:58
Problema Componente tare conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.6 kb
#include <fstream>
#define NMAX 5000
using namespace std;
ifstream fin ("ctc.in");
ofstream fout ("ctc.out");
int n,m, A[NMAX][NMAX],viz[NMAX],nr=1,postordine[NMAX],AT[NMAX][NMAX],sol[2*NMAX],nr2;
void citire();
void afisare();
void parcurgere(int k);
void parcurgere2(int k);
int main()
{
    citire();
   // afisare();
    //fout<<'\n';
    int ok=1,i,cc=0;
    while(ok)
    {ok=0;
     for(i=1;i<=n;i++)
        if(viz[i]==0)
        {ok=1;
         parcurgere(i);
        }
    }
    for(i=n;i>=1;i--)
        if(viz[postordine[i]])
        {
           // fout<<"componenta tare-conexa "<<cc++<<": ";
           cc++;
            parcurgere2(postordine[i]);
            sol[nr2++]=0;
           // fout<<'\n';
        }
    fout<<cc<<'\n';
    for(i=0;i<nr2;i++)
        if(sol[i]) fout<<sol[i]<<" ";
        else fout<<'\n';

    return 0;
}
void citire()
{int x,y;
    fin>>n>>m;
    while(m--)
    {
        fin>>x>>y;
        A[x][0]++;
        A[x][A[x][0]]=y;
        AT[y][0]++;
        AT[y][AT[y][0]]=x;
    }
}
void parcurgere(int k)
{
    viz[k]=1;
    int i;
    for(i=1;i<=A[k][0];i++)
         if(viz[A[k][i]]==0)
                parcurgere(A[k][i]);
    postordine[nr++]=k;
}
void parcurgere2(int k)
{
    viz[k]=0;
    int i;
   // fout<<k<<" ";
    sol[nr2++]=k;
    for(i=1;i<=AT[k][0];i++)
         if(viz[AT[k][i]])
                parcurgere2(AT[k][i]);
}
void afisare()
{int i,j;
    for(i=1;i<=n;i++)
        {fout<<i<<": ";
            for(j=1;j<=A[i][0];j++)
            fout<<A[i][j]<<" ";
            fout<<'\n';
        }
}