Cod sursa(job #2755900)

Utilizator Mihai_BarbuMihai Barbu Mihai_Barbu Data 28 mai 2021 18:40:45
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.47 kb
#include <bits/stdc++.h>

using namespace std;

const int NMAX = 1e5 + 5;

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

vector<int> adj[NMAX];

vector<vector<int>> sccs;

int found[NMAX];
int low[NMAX];

stack<int> node_st;
bool in_st[NMAX];

void dfs(int node, int p, int& tmp) {
    found[node] = low[node] = ++tmp;

    in_st[node] = true;
    node_st.push(node);

    for (auto neigh : adj[node]) {
        if (found[neigh]) {
            if (in_st[neigh]) {
                // neigh is not in another SCC
                low[node] = min(low[node], found[neigh]);
            }

            continue;
        }

        dfs(neigh, node, tmp);

        low[node] = min(low[node], low[neigh]);
    }

    if (low[node] == found[node]) {
        // node - root of SCC
        int curr;
        vector<int> new_scc;

        do {
            curr = node_st.top();

            node_st.pop();
            in_st[curr] = false;

            new_scc.push_back(curr);
        } while (curr != node);

        sccs.push_back(new_scc);
    }
}

int main() {
    int N, M;

    fin >> N >> M;

    int i, x, y;

    for (i = 1; i <= M; ++i) {
        fin >> x >> y;

        adj[x].push_back(y);
    }

    int tmp = 0;
    for (i = 1; i <= N; ++i) {
        if (!found[i]) {
            dfs(i, i, tmp);
        }
    }

    fout << sccs.size() << "\n";

    for (auto scc : sccs) {
        for (auto node : scc) {
            fout << node << " ";
        }
        fout << "\n";
    }

    return 0;
}