Cod sursa(job #3243146)

Utilizator Luca07Nicolae Luca Luca07 Data 16 septembrie 2024 09:06:19
Problema Componente tare conexe Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.79 kb
#include <fstream>
#include<vector>
#include<stack>
#include<algorithm>
using namespace std;

ifstream cin("ctc.in");
ofstream cout("ctc.out");

vector<vector<int>> graph;

vector<int> visited;

void dfs(int u, vector<vector<int>>& graph, stack<int>& sout) {
    visited[u] = true;
    for (auto v : graph[u]) {
        if (!visited[v]) {
            dfs(v, graph, sout);
        }
    }
    sout.push(u);
}

vector<vector<int>> getSCC(int n, int m, vector<vector<int>> graph) {
    stack<int> sout;
    visited = vector<int>(n + 1, false);

    int u, v;
    for (u = 0; u < n; u++) {
        if (!visited[u]) {
            dfs(u, graph, sout);
        }
    }
    
    vector<vector<int>> rgraph= vector<vector<int>>(n+1);

    for (v = 0; v < n; v++) {
        for (auto u : graph[v]) {
            rgraph[u].push_back(v);
        }
    }

    visited = vector<int>(n + 1, false);
    vector<vector<int>> components;

    for (u = 0; u < n; u++) {
        if (!visited[u]) {
            vector<int> vcomp;
            sout = stack<int>();
            dfs(u, rgraph, sout);
            while (!sout.empty()) {
                vcomp.push_back(sout.top()+1);
                sout.pop();
            }
            sort(vcomp.begin(), vcomp.end());
            components.push_back(vcomp);
        }
    }
    return components;
}


int main()
{
    int i, j, n, m,u,v;

    cin >> n >> m;
    graph = vector<vector<int>>(n);
    for (i = 0; i < m; i++) {
        cin >> u >> v;
        u--;
        v--;
        graph[u].push_back(v);
    }


    auto res = getSCC(n, m, graph);

    cout << res.size() << "\n";
    for (auto v : res) {
        for (auto nr : v) {
            cout << nr << " ";
        }
        cout << "\n";
    }

    return 0;
}