Cod sursa(job #3371785)

Utilizator horia_Horia Casuneanu horia_ Data 31 octombrie 2026 18:11:29
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.37 kb
#include <bits/stdc++.h>
#define NMAX 100005

using namespace std;

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

int n, m;
bool viz[NMAX];
vector<vector<int>> sol;
vector<int> muchii[NMAX], st, noduri;
vector<pair<int, int>> perechi;

void citire()
{
    fin >> n >> m; int x, y;
    for (int i = 1; i <= m; ++i)
    {
        fin >> x >> y;
        muchii[x].push_back(y);
        perechi.push_back({x, y});
    }
}

void DFS1(int nod)
{
    viz[nod] = 1;
    for (int i : muchii[nod])
        if (!viz[i])
            DFS1(i);
    st.push_back(nod);
}

void DFS2(int nod)
{
    noduri.push_back(nod);
    viz[nod] = 1;
    for (int i : muchii[nod])
        if (!viz[i])
            DFS2(i);
}

int main()
{
    citire();
    for (int i = 1; i <= n; ++i)
        if (!viz[i])
            DFS1(i);
    reverse(st.begin(), st.end());
    for (int i = 1; i <= n; ++i)
    {
        viz[i] = 0;
        muchii[i].clear();
    }
    for (pair<int, int> i : perechi)
        muchii[i.second].push_back(i.first);
    for (int i : st)
        if (!viz[i])
        {
            noduri.clear();
            DFS2(i);
            sol.push_back(noduri);
        }
    fout << sol.size() << '\n';
    for (vector<int> i : sol)
    {
        for (int j : i)
            fout << j << ' ';
        fout << '\n';
    }
    return 0;
}