Cod sursa(job #1967915)

Utilizator dumbraveanbDumbravean Bogdan dumbraveanb Data 17 aprilie 2017 12:19:32
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.38 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

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

#define Nmax 100005
#define Inf 0x3f3f3f3f

int n, m, idx;
vector<int> L, Idx, c;
vector<bool> InStk;
vector<vector<int>> cc, G;
stack<int> Stk;

void tarj(int nod) {
    L[nod] = Idx[nod] = ++idx;
    InStk[nod] = true;
    Stk.push(nod);

    for(int y : G[nod])
        if(Idx[y] == Inf) {
            tarj(y);
            L[nod] = min(L[nod], L[y]);
        } else if(InStk[y])
            L[nod] = min(L[nod], L[y]);

    if(Idx[nod] == L[nod]) {
        int nod2;
        c.clear();

        do {
            c.push_back(nod2 = Stk.top());
            Stk.pop();
            InStk[nod2] = false;
        } while(nod != nod2);
        cc.push_back(c);
    }
}

int main()
{
    fin >> n >> m;
    G = vector<vector<int>> (n + 1);
    L = vector<int> (n + 1);
    Idx = vector<int> (n + 1, Inf);
    InStk = vector<bool> (n + 1);

    int x, y;
    for(int i = 1; i <= m; ++i) {
        fin >> x >> y;
        G[x].push_back(y);
    }
    for(int i = 1; i <= n; ++i)
        if(Idx[i] == Inf) tarj(i);

    fout << cc.size() << '\n';
    for(int i = 0; i < cc.size(); ++i) {
        for(int x : cc[i])
            fout << x << ' ';
        fout << '\n';
    }
    return 0;
}