Cod sursa(job #1904557)

Utilizator bt.panteaPantea Beniamin bt.pantea Data 5 martie 2017 17:18:50
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.32 kb
#include <bits/stdc++.h>
#define NMAX 100005
#define min(a, b) ( (a > b) ? b : a)
using namespace std;
ifstream f ("ctc.in");
ofstream g ("ctc.out");

vector < int > a[NMAX], aux, idx(NMAX), lowlink(NMAX);
bitset < NMAX > in_stack;
vector < vector < int > > sol;
stack < int > stk;
int n, m, x, y, index;

void tarjan(int nod) {
    idx[nod] = lowlink[nod] = index;
    index++;
    stk.push(nod);
    in_stack[nod] = 1;
    for (unsigned i = 0; i < a[nod].size(); i++) {
        int next = a[nod][i];
        if (!idx[next]) {
            tarjan(next);
            lowlink[nod] = min(lowlink[nod], lowlink[next]);
        } else if (in_stack[next])
            lowlink[nod] = min(lowlink[nod], lowlink[next]);
    }
    if (idx[nod] == lowlink[nod]) {
        int x;
        aux.clear();
        do {
            x = stk.top();
            stk.pop();
            aux.push_back(x);
        } while (x != nod);
        sol.push_back(aux);
    }
}

int main() {
    f>>n>>m;
    while (m--) {
        f>>x>>y;
        a[x].push_back(y);
    }
    for (int i = 1; i <= n; i++)
        if (!idx[i]) tarjan(i);
    g<<sol.size()<<'\n';
    for (unsigned i = 0; i < sol.size(); i++) {
        for (unsigned j = 0; j < sol[i].size(); j++)
            g<<sol[i][j]<<' ';
        g<<'\n';
    }
    return 0;
}