Cod sursa(job #2167562)

Utilizator loo_k01Luca Silviu Catalin loo_k01 Data 13 martie 2018 22:17:18
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include <bits/stdc++.h>
using namespace std;
const int Nmax = 100003;

int N, M;
int ord[Nmax], top;
int nrcc;
vector <int> L[Nmax], T[Nmax], sol[Nmax];
bitset <Nmax> viz;

void Read()
{
    ifstream fin("ctc.in");
    fin >> N >> M;
    int i, x, y;
    for (i = 1; i <= M; i++)
    {
        fin >> x >> y;
        L[x].push_back(y);
        T[y].push_back(x);
    }
    fin.close();
}

void DFS_PLUS(int nod)
{
    viz[nod] = true;
    for (auto i : L[nod])
        if (!viz[i])
            DFS_PLUS(i);
    ord[++top] = nod;
}

void DFS_MINUS(int nod)
{
    viz[nod] = true;
    for (auto i : T[nod])
        if (!viz[i])
            DFS_MINUS(i);
    sol[nrcc].push_back(nod);
}

void CTC()
{
    int i, nod;

    for (i = 1; i <= N; i++)
        if (!viz[i])
            DFS_PLUS(i);

    viz.reset(); /// reinitializare

    while(top)
    {
        nod = ord[top--];
        if (!viz[nod]) /// daca comp conexa a nodului curent nu e determinata
        {
            ++nrcc;
            DFS_MINUS(nod);
        }
    }

    ofstream fout("ctc.out");
    fout << nrcc << "\n";
    for (i = 1; i <= nrcc; i++)
    {

        for (auto it : sol[i])
            fout << it << " ";
        fout << "\n";
    }
    fout.close();
}

int main()
{
    Read();
    CTC();
    return 0;
}