Cod sursa(job #3306501)

Utilizator Luca_georgescuLuca Georgescu Luca_georgescu Data 11 august 2025 12:37:39
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.33 kb
#include <bits/stdc++.h>
#define int long long

using namespace std;

ifstream f("ctc.in");
ofstream g("ctc.out");

const int nmax=3e5+5;
const int mod=1e9+7;
int n,m,x,y,viz[nmax],comp[nmax],a[nmax],ap,mini;

vector <int> gr[nmax],gt[nmax];
stack <int> order;

vector <int> rez[nmax];

void dfs1(int nod)
{
    viz[nod]=true;
    for (int vec:gr[nod] )
        if ( !viz[vec] )
           dfs1(vec);

    order.push(nod);
}

void dfs2(int nod, int cnx)
{
    comp[nod]=cnx;
    for (int vec:gt[nod] )
        if ( comp[vec]==-1 )
           dfs2(vec,cnx);
}


signed main()
{
    f >> n >> m;
    for (int i=1; i<=m; i++ )
    {
        int x,y;
        f >> x >> y;
        gr[x].push_back(y);
        gt[y].push_back(x);
    }

    fill (viz+1,viz+n+1,false);
    for (int i=1; i<=n; i++ )
        if ( !viz[i] )
           dfs1(i);

    fill(comp+1,comp+n+1,-1);
    int cnx=0;

    int ways=1,cost=0;
    while ( !order.empty() )
    {
        int u=order.top();
        order.pop();

        if ( comp[u]==-1 )
        {
            dfs2(u,cnx);
            cnx++;
        }
    }

    g << cnx << '\n';
    for (int i=1; i<=n; i++ )
        rez[comp[i]].push_back(i);

    for (int i=0; i<cnx; i++, g << '\n' )
        for (auto j:rez[i] )
            g << j << " ";
    return 0;
}