Cod sursa(job #1250237)

Utilizator PescaruVictorPescaru Victor PescaruVictor Data 27 octombrie 2014 22:10:54
Problema Componente tare conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.63 kb
#include <fstream>
#define DMAX 100002
#define NMAX 102
using namespace std;

ofstream fout ("ctc.out");

int n, m, nr;
int G[DMAX][NMAX], GT[DMAX][NMAX], M[3][NMAX];
int sol[DMAX][NMAX];
bool uz[3][DMAX], fol[DMAX];

void citire();
void dfs(int poz, int cat, int A[DMAX][NMAX]);
void afisare ();

int main()
{
    int i, j, k;
    citire();
    for(i=1; i<=n; i++)
    {
        if(!fol[i])
        {
            ++nr;
            dfs(i, 0, G);
            dfs(i, 1, GT);
            for(j=1; j<=M[0][0]; ++j)
            {
                for(k=1; k<=M[1][0]; ++k)
                {
                    if(M[0][j]==M[1][k])
                    {
                        sol[nr][++sol[nr][0]]=M[0][j];
                        fol[M[0][j]]=1;
                    }
                }
            }
            M[0][0]=M[1][0]=0;
            for(j=1; j<=n; j++)
                uz[0][j]=uz[1][j]=0;
        }
    }
    afisare();
    return 0;
}

void citire()
{
    ifstream fin ("ctc.in");
    fin>>n>>m;
    int x, y, i;
    for(i=1; i<=m; ++i)
    {
        fin>>x>>y;
        G[x][++G[x][0]]=y;
        GT[y][++GT[y][0]]=x;
    }
    fin.close();
}


void dfs(int poz, int cat, int A[DMAX][NMAX])
{
    uz[cat][poz]=true;
    M[cat][++M[cat][0]]=poz;
    int i;
    for(i=1; i<=A[poz][0]; i++)
    {
        if(!uz[cat][A[poz][i]])
        {
            dfs(A[poz][i], cat, A);
        }
    }
}

void afisare ()
{
    fout<<nr<<'\n';
    int i, j;
    for(i=1; i<=nr; ++i)
    {
        for(j=1; j<=sol[i][0]; ++j)
            fout<<sol[i][j]<<' ';
        fout<<'\n';
    }
}