Cod sursa(job #1250056)

Utilizator Alexandra_MMihaila Alexandra Alexandra_M Data 27 octombrie 2014 19:38:20
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.76 kb
#include <fstream>
#define dmax 100005
#define nmax 1005

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

int n, m, ind;
int G[dmax][nmax], GT[dmax][nmax], sol[dmax][nmax];
int MG[dmax], MGT[dmax], uz1[dmax], uz2[dmax], vsol[dmax];

void citire();
void DFS(int);
void DFST(int);
void gol();
void afisare();

int main()
{
    int i, j, k;
    citire();
    for (i=1; i<=n; i++)
        if (!vsol[i])
        {
            MG[0]=MGT[0]=1;
            MG[1]=MGT[1]=i;
            DFS(i);
            DFST(i);
            for (j=1; j<=MG[0]; j++)
                for (k=1; k<=MGT[0]; k++)
                    if (MG[j]==MGT[k])
                    {
                        sol[ind][++sol[ind][0]]=MG[j];
                        vsol[MG[j]]=1;
                    }
            ind++;
            gol();
        }
    afisare();
    fout.close();
    return 0;
}
void citire()
{
    int i, x, y;
    fin>>n>>m;
    for (i=1; i<=m; i++)
    {
        fin>>x>>y;
        G[x][0]++;
        G[x][G[x][0]]=y;
        GT[y][0]++;
        GT[y][GT[y][0]]=x;
    }
}
void DFS(int x)
{
    int i;
    uz1[x]=1;
    for (i=1; i<=G[x][0]; i++)
        if (!uz1[G[x][i]])
        {
            MG[0]++;
            MG[MG[0]]=G[x][i];
            DFS(G[x][i]);
        }
}
void DFST(int x)
{
    int i;
    uz2[x]=1;
    for (i=1; i<=GT[x][0]; i++)
    {
        MGT[0]++;
        MGT[MGT[0]]=GT[x][i];
        DFST(GT[x][i]);
    }
}
void gol()
{
    int i;
    for (i=1; i<=n; i++)
        uz1[i]=uz2[i]=0;
}
void afisare()
{
    int i, j;
    fout<<ind<<'\n';
    for (i=0; i<ind; i++)
    {
        for (j=1; j<=sol[i][0]; j++)
            fout<<sol[i][j]<<' ';
        fout<<'\n';
    }
}