Cod sursa(job #2080582)

Utilizator AndreiMaximIonutMaxim Andrei AndreiMaximIonut Data 3 decembrie 2017 12:19:54
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
#define pb push_back

int N, M, nr;
vector <int> G[100001], GT[100001], PostOrdine, CTC[100001];
vector <bool> Viz;

void DFS(int x)
{
    int i;

    Viz[x] = true;

    for(i = 0; i < G[x].size(); ++i)
        if(!Viz[G[x][i]]) DFS(G[x][i]);

    PostOrdine.pb(x);
}

void DFST(int x)
{
    int i;

    Viz[x] = false;
    CTC[nr].pb(x);

    for(i = 0; i < GT[x].size(); ++i)
        if(Viz[GT[x][i]] == true) DFST(GT[x][i]);
}
int main()
{
    int i, j, k;

    fin>>N>>M;

    for(k = 1; k <= M; ++k)
    {
        fin>>i>>j;

        G[i].pb(j);
        GT[j].pb(i);
    }

    Viz.assign(N + 1, false);

    for(i = 1; i <= N; ++i)
        if(!Viz[i]) DFS(i);

    for(i = N - 1; i >= 0; --i)
        if(Viz[PostOrdine[i]] == true)
        {
            nr++;
            DFST(PostOrdine[i]);
        }

    fout<<nr<<'\n';
    for(i = 1; i <= nr; ++i)
    {
        for(j = 0; j < CTC[i].size(); ++j)
            fout<<CTC[i][j]<<' ';
        fout<<'\n';
    }

    return 0;
}