Cod sursa(job #3350370)

Utilizator marap2011Paun Mara marap2011 Data 7 aprilie 2026 13:15:29
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.54 kb
#include <bits/stdc++.h>
#define pi pair<int,int>
using namespace std;

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

const int nmx = 1e5 + 5 ;

bool sel[nmx] ;
vector < int > g[nmx] ;
vector < int > gt[nmx] ;

vector < int > st ;

vector < vector < int > > componente ;
vector < int > comp_cur ;

void dfs ( int node )
{
    st.push_back(node) ;
    sel[node] = 1 ;
    for ( auto it : g[node] )
        if ( ! sel[it] )
            dfs ( it ) ;
}

void dfs2 ( int node )
{
    sel[node] = 0 ;
    for ( auto it : gt[node] )
        if ( sel[it] )
            dfs2 ( it ) ;
    comp_cur.push_back(node) ;
}

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

    int cnt = 0 ;
    for ( int i = 1 ; i <= n ; i ++ )
        if ( ! sel[i] )
            dfs ( i ) ;

    for ( int i = st.size() - 1 ; i >= 0 ; i -- )
    {
        int nod = st[i] ;
        if ( sel[nod] )
        {
            comp_cur.clear() ;
            dfs2 ( nod ) ;
            componente.push_back(comp_cur) ;
        }
    }

    fout << componente.size() << '\n' ;
    for ( int i = 0 ; i < componente.size() ; i ++ )
    {
        for ( auto it : componente[i] )
            fout << it << " " ;
        fout << '\n' ;
    }
}

int main()
{
    std :: ios_base :: sync_with_stdio ( false ) ;
    fin.tie(0) ;
    fout.tie(0) ;
    solve() ;

    return 0;
}