Cod sursa(job #2722865)

Utilizator sichetpaulSichet Paul sichetpaul Data 13 martie 2021 12:42:43
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.99 kb
#include <bits/stdc++.h>
#define Nmax 100005
using namespace std;

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

int N, M, K;
bool vis1[Nmax], vis2[Nmax];
vector<int> G[Nmax], GT[Nmax], ctc[Nmax], nodes;

void DFS1(int node) {
    vis1[node] = 1;
    for (auto it: G[node])
        if (!vis1[it]) DFS1(it);
    nodes.push_back(node);
}
void DFS2(int node) {
    vis2[node] = 1;
    ctc[K].push_back(node);
    for (auto it: GT[node])
        if (!vis2[it]) DFS2(it);
}
int main()
{
    fin >> N >> M;
    while (M--) {
        int x, y;
        fin >> x >> y;
        G[x].push_back(y);
        GT[y].push_back(x);
    }

    for (int i = 1; i <= N; ++i)
        if (!vis1[i]) DFS1(i);

    reverse(nodes.begin(), nodes.end());
    for (auto it: nodes)
        if (!vis2[it]) ++K, DFS2(it);

    fout << K << '\n';
    for (int i = 1; i <= K; ++i) {
        for (auto it: ctc[i])
            fout << it << " ";
        fout << '\n';
    }

    return 0;
}