Cod sursa(job #1250879)

Utilizator Alexandra_MMihaila Alexandra Alexandra_M Data 28 octombrie 2014 18:13:04
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.65 kb
//#include <cstdio>
#include <fstream>
#include <vector>

#define DMAX 100005
#define IN "ctc.in"
#define OUT "ctc.out"

using namespace std;
//FILE*fin=fopen(IN,"r");
//FILE*fout=fopen(OUT,"w");
ifstream fin (IN);
ofstream fout (OUT);

void citire();
void dfs(int);
void dfs_transpus(int);
void gol();
void afisare();

vector <int> A[DMAX], T[DMAX], sol[DMAX];
int uz[DMAX], postordine[DMAX];
int n, m, nr, nrcomp;

int main()
{
    int i, j;
    citire();
    for (i=1; i<=n; i++)
        if (!uz[i]) dfs(i);
    gol();
    for (i=n; i>0; i--)
        if (!uz[postordine[i]])
        {
            nrcomp++;
            dfs_transpus(postordine[i]);
            //fprintf(fout,"\n");
            //fout<<'\n';
        }
    fout<<nrcomp<<'\n';
    for (i=1; i<=nrcomp; i++)
    {
        for (j=0; j<sol[i].size();j++)
           fout<<sol[i][j]<<' ';
        fout<<'\n';
     }
    fout.close();
    //fclose(fout);
    return 0;
}
void citire()
{
    int i, x, y;
    //fscanf(fin,"%d %d",&n,&m);
    fin>>n>>m;
    for (i=1; i<=m; i++)
    {
        //fscanf(fin,"%d %d",&x,&y);
        fin>>x>>y;
        A[x].push_back(y);
        T[y].push_back(x);
    }
}
void dfs(int x)
{
    int i;
    uz[x]=1;
    for (i=0; i<A[x].size(); i++)
        if (!uz[A[x][i]])
            dfs(A[x][i]);
    postordine[++nr]=x;
}

void dfs_transpus(int x)
{
    int i;
    //fprintf(fout,"%d ",x);
    //fout<<x<<' ';
    uz[x]=1;
    sol[nrcomp].push_back(x);
    for (i=0; i<T[x].size(); i++)
     if (!uz[T[x][i]])
        dfs_transpus(T[x][i]);
}
void gol()
{
    for (int i=1; i<=n; i++)
        uz[i]=0;
}