Cod sursa(job #2547236)

Utilizator alexilasiAlex Ilasi alexilasi Data 15 februarie 2020 10:20:43
Problema Componente tare conexe Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.2 kb
#include <bits/stdc++.h>

using namespace std;

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

const int nMax = 100010;

int nrctc, t;
vector <int> v[nMax], ct[nMax], disc, low;
stack <int> s;

void ctc(int nod)
{
    t++;
    disc[nod] = low[nod] = t;
    s.push(nod);

    for(auto it : v[nod])
    {
        if(!disc[it])
        {
            ctc(it);
            low[nod] = min(low[nod], low[it]);
        }
        else low[nod] = min(low[nod], disc[it]);
    }

    if(low[nod] == disc[nod])
    {
        while(s.top() != nod)
        {
            ct[nrctc].push_back(s.top());
            s.pop();
        }
        ct[nrctc].push_back(s.top());
        s.pop();
        nrctc++;
    }

}

int main()
{
    int n, m; fin >> n >> m;
    disc.assign(n, 0);
    low.assign(n, 0);
    for(int i=0; i<m; i++)
    {
        int x, y; fin >> x >> y; x--; y--;
        v[x].push_back(y);
    }
    for(int i=0; i<n; i++)
        if(!disc[i])
        {
            ctc(i);
        }
    fout << nrctc << '\n';
    for(int i=0; i<nrctc; i++)
    {
        for(auto it : ct[i])
            fout << it + 1 << " ";
        fout << '\n';
    }
    return 0;
}