Cod sursa(job #1985485)

Utilizator rares96cheseliRares Cheseli rares96cheseli Data 27 mai 2017 23:10:45
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include <bits/stdc++.h>

#define NMAX 100005

using namespace std;

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

int N, M, x, y, components, viz[NMAX];
vector < int > G[NMAX], GT[NMAX], tsort;
vector < int > CTC[NMAX];

void dfs(int node) {
    viz[node] = 1;
    for (auto it : G[node]) {
        if (!viz[it]) {
            dfs(it);
        }
    }

    tsort.push_back(node);
}

void dfs2(int node) {
    viz[node] = 0;
    CTC[components].push_back(node);

    for (auto it : GT[node]) {
        if (viz[it]) {
            dfs2(it);
        }
    }
}

int main() {
    f >> N >> M;
    for (int i = 1; i <= M; ++i) {
        f >> x >> y;
        G[x].push_back(y);
        GT[y].push_back(x);
    }

    for (int i = 1; i <= N; ++i) {
        if (!viz[i]) {
            dfs(i);
        }
    }

    for (int i = N - 1; i >= 0; --i) {
        if (viz[tsort[i]]) {
            dfs2(tsort[i]);
            ++components;
        }
    }

    g << components << '\n';
    for (int i = 0; i < components; ++i) {
        sort(CTC[i].begin(), CTC[i].end());
        for (auto it : CTC[i]) {
            g << it << ' ';
        }

        g << '\n';
    }
    return 0;
}