Cod sursa(job #1250475)

Utilizator andreea.ciobanuCiobanu Andreea andreea.ciobanu Data 28 octombrie 2014 10:19:13
Problema Componente tare conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.37 kb
#include <fstream>
#include <vector>
#define NMAX 10000

using namespace std;

ifstream fin ("ctc.in");
ofstream fout ("ctc.out");

int org[NMAX][NMAX], trs[NMAX][NMAX];
int uz[NMAX], post[NMAX];
int n, m, lg, comp;

void citire();
void dfs_initial(int);
void dfs_transpus(int);
void afisare();

int main()
{
    int i, j;
    citire();
    for (i=1; i<=n; ++i)
        if (uz[i]==0)
            dfs_initial(i);
    for(i=1; i<=n; i++)
        uz[i]=0;
    for(i=n; i>=1; i--)
        if(uz[post[i]]==0)
            {
            comp++;
            dfs_transpus(post[i]);
            }
    afisare();
    return 0;
}
void citire()
{
    int x,y,i;
    fin>>n>>m;
    for(i=1; i<=m; i++)
        {
        fin>>x>>y;
        org[x][++org[x][0]]=y;
        trs[y][++trs[y][0]]=x;
        }
}
void dfs_initial (int k)
{
    int i;
    uz[k]=1;
    for (i=1; i<=org[k][0]; i++)
        if (uz[org[k][i]]==0)
            dfs_initial(org[k][i]);
    post[++lg]=k;
}
void dfs_transpus (int k)
{
    int i;
    uz[k]=comp;
    for (i=1; i<=trs[k][0]; i++)
        if (uz[trs[k][i]]==0)
            dfs_transpus(trs[k][i]);

}
void afisare()
{
    int i, j;
    fout<<comp<<'\n';
    for(i=1; i<=comp; i++)
        {
        for(j=1; j<=n; j++)
            if(uz[j]==i)
                fout<<j<<' ';
        fout<<'\n';
        }
}