Cod sursa(job #2645762)

Utilizator WholeGrainAndy N WholeGrain Data 29 august 2020 15:35:42
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.63 kb
#include <iostream>
#include <vector>
#include <stack>
#include <fstream>

using namespace std;

#define CAP 100001

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

int n, m;

vector<int> graph[CAP];

int isStack[CAP];

stack<int> s;

bool visited[CAP];

int tm[CAP];

int boss[CAP];

int t = 0;

vector<int> sol[CAP];

int sz = 0;

void dfsScc(int v) {
    visited[v] = true;

    t++;

    boss[v] = t;

    tm[v] = t;

    isStack[v] = true;

    s.push(v);

    for (int i = 0; i < graph[v].size(); i++) {
        if (!visited[graph[v][i]]) {
            dfsScc(graph[v][i]);
        }

        if (isStack[graph[v][i]] && boss[graph[v][i]] < boss[v]) {
            boss[v] = boss[graph[v][i]];
        }
    }

    if (tm[v] == boss[v]) {
        while (s.top() != v) {
            int curr = s.top();

            s.pop();

            isStack[curr] = false;

            sol[sz].push_back(curr + 1);

            //out << curr + 1 << " ";
        }

        if (s.top() == v) {
            isStack[s.top()] = false;

            sol[sz].push_back(s.top() + 1);

            //out << s.top() + 1 << " ";

            s.pop();
        }

        sz++;

        //out << '\n';
    }
}

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

    for (int i = 0; i < m; i++) {
        int u, v;

        in >> u >> v;

        u--;

        v--;

        graph[u].push_back(v);
    }

    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            dfsScc(i);
        }
    }

    out << sz << '\n';

    for (int i = 0; i < sz; i++) {
        for (int j = 0; j < sol[i].size(); j++) {
            out << sol[i][j] << " ";
        }

        out << '\n';
    }

    return 0;
}