Cod sursa(job #3296201)

Utilizator CosminaneBoac Mihai Cosmin Cosminane Data 12 mai 2025 10:03:18
Problema Componente tare conexe Scor 100
Compilator cpp-32 Status done
Runda Arhiva educationala Marime 1.28 kb
#include <bits/stdc++.h>
using namespace std;
vector <int> v[100005][2], stiva, comp;
vector <vector <int>> ras;
int f[100005];
void dfs( int x, int tip ){
    int i, y;
    if( tip == 1 ){
        comp.push_back( x );
    }
    for( i = 0; i < v[x][tip].size(); i++ ){
        y = v[x][tip][i];
        if( f[y] != f[x] ){
            f[y]++;
            dfs( y, tip );
        }
    }
    if( tip == 0 ){
        stiva.push_back( x );
    }
}
int main(){
    int n, m, i, j, x, y;
    ifstream fin( "ctc.in" );
    ofstream fout( "ctc.out" );
    fin >> n >> m;
    for( i = 0; i < m; i++ ){
        fin >> x >> y;
        v[x][0].push_back( y );
        v[y][1].push_back( x );
    }
    for( i = 1; i <= n; i++ ){
        if( f[i] == 0 ){
            f[i]++;
            dfs( i, 0 );
        }
    }
    for( i = stiva.size() - 1; i >= 0; i-- ){
        if( f[stiva[i]] == 1 ){
            f[stiva[i]]++;
            dfs( stiva[i], 1 );
            ras.push_back( comp );
            comp.clear();
        }
    }
    ///cout << "AJUNS\n";
    fout << ras.size() << '\n';
    for( i = 0; i < ras.size(); i++ ){
        for( j = 0; j < ras[i].size(); j++ ){
            fout << ras[i][j] << ' ';
        }
        fout << '\n';
    }
    return 0;
}