Cod sursa(job #3271716)

Utilizator stefypluStefan Plugaru stefyplu Data 27 ianuarie 2025 08:22:22
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.19 kb
//#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream cin("ctc.in");
ofstream cout("ctc.out");
int n, m, a, b, vf;
bool used[100003];
vector <int> g[200003];
vector <int> gt[200003];
vector <int> ctc[100003];
vector <int> sortop;
void dfs(int x)
{
    used[x]=1;
    for (auto e:g[x])
        if (used[e]==0)
            dfs(e);
    sortop.push_back(x);
}
void dfs2(int x)
{
    used[x]=1;
    ctc[vf].push_back(x);
    for (auto e : gt[x])
        if (used[e]==0)
            dfs2(e);
}
int main()
{
    cin>>n>>m;
    for (int i=1; i<=m; i++)
    {
        cin>>a>>b;
        g[a].push_back(b);
        gt[b].push_back(a);
    }
    for (int i=1; i<=n; i++)
        if (used[i]==0)
            dfs(i);
    reverse(sortop.begin(), sortop.end());
    for (int i=1; i<=n; i++)
        used[i]=0;
    for (auto e : sortop)
        if (used[e]==0)
        {
            vf++;
            dfs2(e);
        }
    cout<<vf<<'\n';
    for (int i=1; i<=vf; i++)
    {
        sort(ctc[i].begin(), ctc[i].end());
        for (auto e: ctc[i])
            cout<<e<<' ';
        cout<<'\n';
    }
    return 0;
}