Cod sursa(job #3320336)

Utilizator code_blocksSpiridon Mihnea-Andrei code_blocks Data 5 noiembrie 2025 02:55:52
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.21 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <deque>
#include <algorithm>
#include <utility>

using namespace std;

int N, M, k = 0;
vector<int> G[100001], Gt[100001], ctc[100001];
deque<int> T;
bool viz[100001];

void topsort_dfs(int u)
{
    viz[u] = true;
    for(const auto& v : G[u])
        if(!viz[v])
            topsort_dfs(v);

    T.push_front(u);
}

void clear_viz()
{
    for(int i = 1; i <= N; i++) 
        viz[i] = false;
}

void flag_ctc(int u)
{
    viz[u] = true;
    ctc[k].push_back(u);

    for(const auto& v : Gt[u])
        if(!viz[v])
            flag_ctc(v);
}

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

    fin >> N >> M;
    for(int i = 1; i <= M; i++)
    {
        int a, b;
        fin >> a >> b;
        G[a].push_back(b);
        Gt[b].push_back(a);
    }

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

    clear_viz();

    for(const auto& u : T)
        if(!viz[u])
            k++, flag_ctc(u);

    fout << k << '\n';
    for(int i = 1; i <= k; i++)
    {
        for(const auto& u : ctc[i])
            fout << u << ' ';
        fout << '\n';
    }

    fin.close();
    fout.close();

    return 0;
}