Cod sursa(job #3271056)

Utilizator AsandeiStefanAsandei Stefan-Alexandru AsandeiStefan Data 25 ianuarie 2025 09:49:31
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.39 kb
#include <unordered_map>
#include <fstream>
#include <vector>
#include <stack>

const int nmax = 1e5;

using namespace std;

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

int n, m, x, y;
vector<int> g[nmax + 1], gt[nmax + 1];
bool visited[nmax + 1];
stack<int> finished;
unordered_map<int, vector<int>> scc;

void dfs(int node, vector<int> graph[], bool collect = true, int scc_index = -1) {
    visited[node] = true;

    if(scc_index != -1) {
        scc[scc_index].push_back(node);
    }

    for (int child : graph[node]) {
        if (!visited[child]) {
            dfs(child, graph, collect, scc_index);
        }
    }

    if (collect) {
        finished.push(node);
    }
}

int kosaraju() {
	int scc_count = 0;

    for (int i = 1; i <= n; i++) {
        if (!visited[i]) {
            dfs(i, g);
        }
    }

    fill(visited, visited + n + 1, false);

    while (!finished.empty()) {
        int node = finished.top();
        finished.pop();

        if (!visited[node]) {
            dfs(node, gt, false, scc_count);
            scc_count++;
        }
    }

    return scc_count;
}


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

    while (m--) {
        fin >> x >> y;
        g[x].push_back(y);
        gt[y].push_back(x);
    }

    fout << kosaraju() << '\n';
    for(auto kv: scc) {
        for(auto node: kv.second) {
            fout << node << ' ';
        }
        fout << '\n';
    }
    return 0;
}