Cod sursa(job #3186977)

Utilizator NutaAlexandruASN49K NutaAlexandru Data 26 decembrie 2023 20:13:56
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.33 kb
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(),x.end()
#define pb push_back
#define bug(x) cerr<<#x<<" ( "<<x<<endl
using i64=long long;
const int inf=1e9;
void dfs(const int nod,const vector<vector<int>>& g,vector<int>& add_to,vector<bool>&viz)
{
    if(viz[nod])
    {
        return;
    }
    viz[nod]=true;
    for(auto &c:g[nod])
    {
        dfs(c,g,add_to,viz);
    }
    add_to.pb(nod);
}
main()
{
    ifstream cin("ctc.in");
    ofstream cout("ctc.out");
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,m;
    cin>>n>>m;
    vector<vector<int>>g(n);
    vector<vector<int>>gr(n);
    for(int i=0;i<m;i++)
    {
        int x,y;
        cin>>x>>y;
        x--;
        y--;
        g[x].pb(y);
        gr[y].pb(x);
    }
    vector<int>order;
    vector<bool>viz(n,false);
    for(int i=0;i<n;i++)
    {
        dfs(i,g,order,viz);
    }
    vector<vector<int>>sol;
    for(int i=0;i<n;i++)
        viz[i]=false;
    for(int i=n-1;i>=0;i--)
    {
        if(!viz[order[i]])
        {
            vector<int>aux;
            dfs(order[i],gr,aux,viz);
            sol.pb(aux);
        }
    }
    cout<<sol.size()<<'\n';
    for(auto &v:sol)
    {
        for(auto &c:v)
        {
            cout<<c+1<<' ';
        }
        cout<<'\n';
    }
}