Cod sursa(job #2144553)

Utilizator LittleWhoFeraru Mihail LittleWho Data 26 februarie 2018 19:58:59
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.5 kb
#include <bits/stdc++.h>

using namespace std;

#define NMAX 100005

vector<int> adj[NMAX];
int lowlink[NMAX];
int idx[NMAX];
bitset<NMAX> in_stack;
vector<int> component;
vector<vector<int>> sol;
stack<int> S;
int indecs;

int n, m;

void tarjan(int node) {
    idx[node] = lowlink[node] = indecs++;
    S.push(node);
    in_stack[node] = true;

    for (auto &next_node: adj[node]) {
        if (idx[next_node] == -1) {
            tarjan(next_node);
            lowlink[node] = min(lowlink[node], lowlink[next_node]);
        } else if (in_stack[next_node]) {
            lowlink[node] = min(lowlink[node], lowlink[next_node]);
        }
    }

    if (idx[node] == lowlink[node]) {
        component.clear();
        int another_node;
        do {
            component.push_back(another_node = S.top());
            S.pop();
            in_stack[another_node] = 0;
        } while (another_node != node);
        sol.push_back(component);
    }
}

int main() {
    freopen("carici.in", "r", stdin);

    freopen("ctc.in", "r", stdin);
    freopen("ctc.out", "w", stdout);

    scanf("%d%d",&n, &m);

    int x, y;
    for (int i = 0 ; i < m ;i++) {
        scanf("%d%d", &x, &y);
        adj[x].push_back(y);
    }

    for (int i = 1; i <= n; i++)
        idx[i] = -1;
    for (int i = 1; i <= n; i++)
        if (idx[i] == -1) tarjan(i);

    cout << sol.size() << "\n";
    for (auto &s: sol) {
        sort(s.begin(), s.end());
        for (auto &i: s) {
            cout << i << " ";
        } cout << "\n";
    }

    return 0;
}