Cod sursa(job #1042280)

Utilizator gabriela-ivascuIvascu Gabriela gabriela-ivascu Data 26 noiembrie 2013 20:38:25
Problema Componente tare conexe Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 2.44 kb
#include<cstdio>
#include<vector>
#define NMAX 100000
using namespace std;
FILE* fin=fopen("ctc.in", "r");
FILE* fout=fopen("ctc.out", "w");
int n,m,nr,nrctc;
int viz[NMAX],postordine[NMAX];
vector<int> G[NMAX];
vector<int> GT[NMAX];
vector<int> ma[NMAX];
/*
//varianta 1
int D[NMAX][NMAX],n,viz[NMAX],m,x,y;
void citire()
{
    int i,j;
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y;
        D[x][y]=1;
    }
}
void construire()
{
    int i,j,k;
    for(k=1;k<=n;k++)
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
                if(D[i][k] && D[k][j])
                    D[i][j]=1;
}
void rezolvare(int x)
{
    int i,j;
    for(j=1;j<=n;j++)
    {
        if(viz[j]==0)
        {
            viz[j]=1;
            fout<<j<<" ";
            for(i=1;i<=n;i++)
            {
                if(D[j][i]==1 && D[i][j]==1 && viz[i]==0)
                {
                    viz[i]=1;
                    fout<<i<<" ";
                }
            }
            fout<<"\n";
        }

    }
}

int main()
{
    citire();
    construire();
    rezolvare(1);
}*/
void citire() //citire
{
    int i,x,y;
    fscanf(fin,"%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
        fscanf(fin,"%d%d",&x,&y);
        G[x].push_back(y); //graf
        GT[y].push_back(x); //graful transpus
    }
}
void DFS(int vf)
{
    int i;
    viz[vf]=1;
    for(i=0;i<G[vf].size();i++)
        if(viz[G[vf][i]]==0) //daca vf nu a fost vizitat mai fac un DFS.
            DFS(G[vf][i]);
    postordine[++nr]=vf; //pun vf in vectorul postordine cand nu mai am noduri accesibile
}
void DFST(int vf)
{
    int i;
    viz[vf]=0;
    ma[nrctc].push_back(vf);
    for(i=0;i<GT[vf].size();i++)
        if(viz[GT[vf][i]]==1)
            DFST(GT[vf][i]);

}
void afisare()
{
    int i,j;
    fprintf(fout,"%d",nrctc);
    fprintf(fout,"%s","\n");
    for(i=0;i<nrctc;i++)
    {
        for(j=0;j<ma[i].size();j++)
            fprintf(fout,"%d ",ma[i][j]);

        fprintf(fout,"%s","\n");
    }

}
int main()
{
    int i;
    citire();
    for(i=1;i<=n;i++)
        if(viz[i]==0) //daca vf nu a fost vizitat fac DFS
            DFS(i);

    for(i=n;i>=1;i--) //parcurg vectorul postordine de la dreapta la stanga
        if(viz[postordine[i]]==1)  //daca vf
        {
            DFST(postordine[i]);
            nrctc++; //cresc nr de componente
        }

    afisare();
return 0;
}