Cod sursa(job #1249761)

Utilizator Arodoet96Teodora Stoleru Arodoet96 Data 27 octombrie 2014 13:40:39
Problema Componente tare conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.58 kb
#include <fstream>
#define NMAX 5004
#define DMAX 1000

using namespace std;

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

int n, m;
bool g[NMAX][DMAX], gt[NMAX][DMAX];
bool a[NMAX], at[NMAX];
bool uz[NMAX], ctc[NMAX];
int c[NMAX][NMAX], nrctc;

void citire();
void tareconex();
void dfs(int vf, bool d[NMAX][DMAX], bool a[NMAX]);
void afisare();

int main()
{
    citire();
    tareconex();
    afisare();
    return 0;
}

void citire()
{
    int i, x, y;
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y;
        g[x][y]=1;
        gt[y][x]=1;
    }
    for(i=1;i<=n;i++)
        g[i][i]=gt[i][i]=1;
}

void tareconex()
{
    int i, j;
    for(i=1;i<=n;i++)
        if(!ctc[i])
        {
            ctc[i]=1;
            ++nrctc;

            for(j=1;j<=n;j++)
                a[j]=uz[j]=0;
            a[i]=1; uz[i]=1;
            dfs(i, g, a);

            for(j=1;j<=n;j++)
                at[j]=uz[j]=0;
            at[i]=1; uz[i]=1;
            dfs(i, gt, at);

            for(j=1;j<=n;j++)
                if(a[j]&&at[j])
                {
                    ctc[j]=1;
                    c[nrctc][++c[nrctc][0]]=j;
                }
        }
}

void dfs(int vf, bool d[NMAX][DMAX], bool a[NMAX])
{
    int i;

    a[vf]=1;
    uz[vf]=1;

    for(i=1;i<=n;i++)
        if(!uz[i] && d[vf][i])
            dfs(i, d, a);
}

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