Cod sursa(job #3337787)

Utilizator MMEnisEnis Mutlu MMEnis Data 30 ianuarie 2026 08:18:08
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.41 kb
#include <bits/stdc++.h>

using namespace std;

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

int n, m;
vector <int> adj[100001], adj2[100001];
queue <int> q;
vector <int> lista;
bool fr[100001];
map <int, vector <int> > mapa;

void dfs( int c )
{
    fr[c] = 1;
    for ( int i = 0; i < adj[c].size(); i ++ )
    {
        int l = adj[c][i];
        if ( fr[l] == 0 )
        {
            dfs(l);
            lista.push_back(l);
        }
    }
}

void append( int c, int root )
{
    fr[c] = 1;
    mapa[root].push_back(c);
    for ( int i = 0; i < adj2[c].size(); i ++ )
    {
        int l = adj2[c][i];
        if ( fr[l] == 0 )
            append( l, root );
    }
}

int main()
{
    f >> n >> m;
    for ( int i = 1; i <= m; i ++ )
    {
        int x, y;
        f >> x >> y;
        adj[x].push_back(y);
        adj2[y].push_back(x);
    }
    dfs(1);
    for ( int i = 1; i <= n; i ++ )
    {
        if( fr[i] == 0 )
            lista.push_back(i);
        fr[i] = 0;
    }

    for ( int i = lista.size() - 1; i >= 0; i -- )
        if ( fr[lista[i]] == 0 )
            append ( lista[i], lista[i] );
    g << mapa.size() << '\n';
    for ( auto it = mapa.begin(); it != mapa.end(); it ++ )
    {
        int idx = it -> first;
        for ( int i = 0; i < mapa[idx].size(); i ++ )
            g << mapa[idx][i] << " ";
        g << '\n';
    }
    return 0;
}