Cod sursa(job #1248600)

Utilizator gabrieligabrieli gabrieli Data 25 octombrie 2014 16:46:23
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 kb
#include <algorithm>
#include <fstream>
#include <iterator>
#include <vector>
using namespace std;

void dfs(
        const int v,
        vector<bool>& visited,
        vector<int>& topological_order,
        const vector<vector<int>>& G) {
    visited[v] = true;
    for (int u : G[v]) if (!visited[u])
        dfs(u, visited, topological_order, G);
    topological_order.push_back(v);
}

int main() {
    ifstream fin("ctc.in");
    ofstream fout("ctc.out");
    
    int n, m; fin >> n >> m;
    vector<vector<int>> G(n), rG(n);
    for (; m; --m) {
        int u, v; fin >> u >> v;
        G[u - 1].push_back(v - 1);
        rG[v - 1].push_back(u - 1);
    }
    
    vector<bool> visited(n, false);
    vector<int> topological_order;
    
    for (int v = 0; v < n; ++v) if (!visited[v])
        dfs(v, visited, topological_order, G);
    
    fill(visited.begin(), visited.end(), false);
    vector<vector<int>> ctc;
    for (auto v = topological_order.rbegin(); v < topological_order.rend(); v++)
        if (!visited[*v]) {
            ctc.push_back(vector<int>());
            dfs(*v, visited, ctc.back(), rG);
        }
    
    fout << ctc.size() << '\n';
    for (vector<int>& c : ctc) {
        for (int v : c)
            fout << v+1 << ' ';
        fout << '\n';
    }
    
    return 0;
}