Cod sursa(job #3295147)

Utilizator DrugeaCasiandrugea DrugeaCasian Data 2 mai 2025 19:20:55
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.81 kb
#include <iostream>
#include <vector>
#include <stack>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

int n, m;
vector<vector<int>> adj;
vector<vector<int>> adjT;
vector<bool> visited;
stack<int> finish_stack;
vector<vector<int>> sccs;

void dfs1(int u) {
    visited[u] = true;
    for (int v : adj[u]) {
        if (!visited[v]) {
            dfs1(v);
        }
    }
    finish_stack.push(u);
}

void dfs2(int u, vector<int>& current_scc) {
    visited[u] = true;
    current_scc.push_back(u);
    for (int v : adjT[u]) {
        if (!visited[v]) {
            dfs2(v, current_scc);
        }
    }
}

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

    fin >> n >> m;

    adj.resize(n + 1);
    adjT.resize(n + 1);
    visited.resize(n + 1);

    for (int i = 0; i < m; ++i) {
        int u, v;
        fin >> u >> v;
        adj[u].push_back(v);
    }

    fill(visited.begin(), visited.end(), false);
    for (int i = 1; i <= n; ++i) {
        if (!visited[i]) {
            dfs1(i);
        }
    }

    for (int u = 1; u <= n; ++u) {
        for (int v : adj[u]) {
            adjT[v].push_back(u);
        }
    }

    fill(visited.begin(), visited.end(), false);
    while (!finish_stack.empty()) {
        int u = finish_stack.top();
        finish_stack.pop();

        if (!visited[u]) {
            vector<int> current_scc;
            dfs2(u, current_scc);
            sccs.push_back(current_scc);
        }
    }

    fout << sccs.size() << "\n";
    for (vector<int> scc : sccs) {
        sort(scc.begin(), scc.end());
        for (size_t i = 0; i < scc.size(); ++i) {
            fout << scc[i] << (i == scc.size() - 1 ? "" : " ");
        }
        fout << "\n";
    }

    return 0;
}