Cod sursa(job #2695617)

Utilizator ihorvaldsTudor Croitoru ihorvalds Data 13 ianuarie 2021 22:36:46
Problema Componente tare conexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.41 kb
#include <fstream>
#include <algorithm>
#include <unordered_map>
#include <vector>
#include <stack>

using namespace std;

#define list vector<int>

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

int n, m;
unordered_map<int, list> g;
unordered_map<int, list> g_inv;
unordered_map<int, list> components;
list visited;
list used;
stack<int> L;

void read() {
    in >> n >> m;

    int a, b;
    for(int i = 0; i < m; i++) {
        in >> a >> b;
        g[a].push_back(b);
        g_inv[b].push_back(a);
    }

}

void Visit(int u) {
    if (!visited[u]) {
        visited[u] = 1;

        for (auto& v : g[u]) {
            Visit(v);
        }

        L.push(u);
    }
}

void Assign(int u, int root) {
    if (!used[u]) {
        components[root].push_back(u);
        used[u] = 1;

        for(auto& v : g_inv[u]) {
            Assign(v, root);
        }
    }

}


int main() {
    read();
    
    visited = list(n+1, { 0 });
    used = list(n+1, { 0 });

    unordered_map<int, list>::iterator it = g.begin();

    for(; it != g.end(); it++) {
        Visit(it->first);
    }

    while (!L.empty()) {
        int c = L.top();
        L.pop();

        Assign(c, c);
    }

    it = components.begin();

    out << components.size() << '\n';

    for (; it != components.end(); it++) {
        for(size_t i = 0; i < it->second.size(); i++) {
            out << it->second[i] << ' ';
        }
        out << '\n';
    }

    return 0 ;
}