Cod sursa(job #2924870)

Utilizator RobertuRobert Udrea Robertu Data 12 octombrie 2022 19:43:21
Problema Componente tare conexe Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.36 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#define dim 100002
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");

int n, m, a, b, cnt = 0, id = 0;
vector< vector<int> > lists(dim);
vector<bool> onStack(dim);
vector<int> low(dim), disc(dim);
stack<int> stk;

void tarjan(int nod) {
    stk.push(nod);
    onStack[nod] = true;
    disc[nod] = low[nod] = ++id;

    for (int i = 0; i < lists[nod].size(); i++) {
        int vecin = lists[nod][i];

        if (disc[vecin] == 0) {
            tarjan(vecin);
        }

        if( onStack[vecin] ) {
            low[nod] = min(low[nod], low[vecin]);
        }
    }

    if (disc[nod] == low[nod]) {
        while (stk.top() != nod) {
            onStack[stk.top()] = false;
            low[stk.top()] = disc[nod];
            stk.pop();
        }

        onStack[stk.top()] = false;
        low[stk.top()] = disc[nod];
        stk.pop();

        cnt++;
    }
}

int main() {
    fin >> n >> m;

    for (int i = 0; i < m; i++) {
        fin >> a >> b;
        lists[a].push_back(b);
    }

    for (int i = 1; i <= n; i++) {
        if (disc[i] == 0) {
            tarjan(i);
        }
    }

    fout << cnt << "\n" << 1;

    for(int i = 2; i <= n; i++) {
        if( low[i] == low[i - 1] )
            fout << " " << i;
        else fout << '\n' << i;
    }

    fout << '\n';

    return 0;
}