Cod sursa(job #2811035)

Utilizator Ionut10Floristean Ioan Ionut10 Data 30 noiembrie 2021 22:20:49
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.15 kb
#include <bits/stdc++.h>
#define NMax 100000

using namespace std;

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

int n, m;
int u, v;
int nr;
vector<int> adj1[NMax + 1], adj2[NMax + 1];
int comp[NMax + 1];
bool viz1[NMax + 1];
stack<int> st;
vector<int> ans[NMax + 1];

void dfs1 ( int v )
{
    viz1[v] = 1;
    for ( auto u: adj1[v] )
        if ( !viz1[u] )
            dfs1(u);
    st.push(v);
}

void dfs2 ( int v )
{
    comp[v] = nr;
    ans[nr].push_back(v);
    for ( auto u: adj2[v] )
        if ( !comp[u] )
            dfs2(u);
}

int main()
{
    fin >> n >> m;
    for ( int i = 1; i <= m; i++ )
    {
        fin >> u >> v;
        adj1[u].push_back(v);
        adj2[v].push_back(u);
    }

    for ( int i = 1; i <= n; i++ )
        if ( !viz1[i] )
            dfs1(i);

    while ( !st.empty() )
    {
        int x = st.top(); st.pop();
        if ( !comp[x] )
        {
            nr++;
            dfs2(x);
        }
    }
    fout << nr << '\n';
    for ( int i = 1; i <= nr; i++ )
    {
        for ( auto x: ans[i] ) fout << x << " ";
        fout << '\n';
    }
    return 0;
}