Cod sursa(job #1810260)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 19 noiembrie 2016 20:12:42
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 100000 + 1;

vector<int> G[MAX_N];
vector<int> GT[MAX_N];
vector<int> comp[MAX_N];

bool visited[MAX_N];
vector<int> postorder;

int N, M, C;

void dfs(int node){
    visited[node] = true;

    for (int son : G[node])
        if (!visited[son])
            dfs(son);

    postorder.push_back(node);
}

void dfsT(int node){
    visited[node] = false;

    for (int son : GT[node])
        if (visited[son])
            dfsT(son);

    comp[C].push_back(node);
}

void CTC(){
    for (int i = 1; i <= N; i++)
        if (!visited[i])
            dfs(i);

    reverse(postorder.begin(), postorder.end());

    for (int node : postorder){
        if (visited[node]){
            C++;
            dfsT(node);
        }
    }
}

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

    in >> N >> M;

    for (int i = 0; i < M; i++){
        int u, v;
        in >> u >> v;

        G[u].emplace_back(v);
        GT[v].emplace_back(u);
    }

    CTC();

    out << C << "\n";

    for (int i = 1; i <= C; i++){
        for (int x : comp[i])
            out << x << " ";

        out << "\n";
    }

    return 0;
}