Cod sursa(job #2198637)

Utilizator gabib97Gabriel Boroghina gabib97 Data 24 aprilie 2018 21:13:48
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include <bits/stdc++.h>

#define N 100001

using namespace std;

int low[N], ind[N], c_index;
bool in_stack[N];
vector<int> G[N];
vector<vector<int>> sol;
stack<int> S;

void DFS(int s) {
    ind[s] = ++c_index;
    low[s] = c_index;
    S.push(s);
    in_stack[s] = true;

    for (int &x : G[s])
        if (!ind[x]) {
            DFS(x);
            low[s] = min(low[s], low[x]);
        } else if (in_stack[x]) // x is in the same SCC as s
            low[s] = min(low[s], ind[x]);

    if (low[s] == ind[s]) // pop SCC from stack
    {
        int x;
        vector<int> comp;
        do {
            x = S.top();
            S.pop();
            in_stack[x] = false;
            comp.push_back(x);
        } while (x != s);
        sol.push_back(comp);
    }
}

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

    int n, m, x, y;
    scanf("%i%i", &n, &m);
    while (m--) {
        scanf("%i%i", &x, &y);
        G[x].push_back(y);
    }

    for (int i = 1; i <= n; i++)
        if (!ind[i])
            DFS(i);

    // print solution
    printf("%lu\n", sol.size());
    for (auto &v : sol) {
        for (int &x : v) printf("%i ", x);
        printf("\n");
    }
    return 0;
}