Cod sursa(job #2378381)

Utilizator AndreiVisoiuAndrei Visoiu AndreiVisoiu Data 12 martie 2019 09:36:58
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.07 kb
#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 100001;
int N, M, nrC;

vector<int> A[NMAX], AT[NMAX], lst[NMAX], postOrd;
bool v[NMAX];

void dfs(const int& i) {
    v[i] = 1;
    for(const auto& vec: A[i])
        if(!v[vec])
            dfs(vec);

    postOrd.push_back(i);
}

void dfsT(const int& i) {
    v[i] = 0;
    lst[nrC].push_back(i);
    for(const auto& vec: AT[i])
        if(v[vec])
            dfsT(vec);
}
int main()
{
    in >> N >> M;

    postOrd.reserve(N+1);
    int x, y;
    for(int i = 1; i <= M; i++) {
        in >> x >> y;
        A[x].push_back(y);
        AT[y].push_back(x);
    }

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

    for(int i = N-1; i >= 0; i--)
        if(v[postOrd[i]]) {
            nrC++;
            dfsT(postOrd[i]);
        }

    out << nrC << '\n';
    for(int i = 1; i <= nrC; i++) {
        for(const auto& j: lst[i])
            out << j << ' ';
        out << '\n';
    }
    return 0;
}