Cod sursa(job #2132067)

Utilizator KemyKoTeo Virghi KemyKo Data 15 februarie 2018 13:20:44
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include <fstream>
#include <vector>
#include <cstring>
#define NMAX 101011

using namespace std;

ifstream f("ctc.in");
ofstream g("ctc.out");

int SZ;
int n, m, k, sol;
bool viz[NMAX];
vector <int> A[NMAX], B[NMAX], REZ[NMAX];
int path[NMAX];

void DF1(int nod)
{
    int i, sz = A[nod].size();

    viz[nod] = true;
    for(i=0;i<sz;++i)
        if(!viz[A[nod][i]])
            DF1(A[nod][i]);

    path[++k] = nod;
}

void DF2(int nod)
{
    int i, sz = B[nod].size();

    viz[nod] = true;
    for(i=0;i<sz;++i)
        if(!viz[B[nod][i]])
            DF2(B[nod][i]);

    REZ[sol].push_back(nod);
}

int main()
{
    int i, j, sz, x, y;

    f>>n>>m;
    SZ = (n+1) * sizeof(int);
    for(i=1;i<=m;++i){
        f>>x>>y;

        A[x].push_back(y);
        B[y].push_back(x);
    }

    for(i=1;i<=n;++i)
        if(!viz[i])
            DF1(i);

    memset(viz, 0, sizeof(viz));

    for(i=k;i>=1;--i)
        if(!viz[path[i]]){
            ++sol;
            DF2(path[i]);
        }

    g<<sol<<'\n';
    for(i=1;i<=sol;++i){
        sz = REZ[i].size();
        for(j=0;j<sz;++j)
            g<<REZ[i][j]<<' ';
        g<<'\n';
    }

    return 0;
}