Cod sursa(job #3243148)

Utilizator Luca07Nicolae Luca Luca07 Data 16 septembrie 2024 09:11:29
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.71 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, vector<int>& vout) {
    visited[u] = true;
    for (auto v : graph[u]) {
        if (!visited[v]) {
            dfs(v, graph, vout);
        }
    }
    vout.push_back(u);
}

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

    int u, v;
    for (u = 0; u < n; u++) {
        if (!visited[u]) {
            dfs(u, graph, vout);
        }
    }
    
    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 (auto it = vout.rbegin(); it != vout.rend(); it++) {
        if (!visited[*it]) {
            vector<int> vcomp;
            vector<int> vout2;
            dfs(*it, rgraph, vout2);
            sort(vout2.begin(), vout2.end());
            components.push_back(vout2);
        }
    }
    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+1 << " ";
        }
        cout << "\n";
    }

    return 0;
}