Cod sursa(job #2853491)

Utilizator Casian_doispeChiriac Casian Casian_doispe Data 20 februarie 2022 12:45:26
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.57 kb
#include <fstream>
#include <deque>
#include <vector>
#include <bitset>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cstring>

#define MOD 1000000007

using namespace std ;

ifstream cin ("ctc.in") ;
ofstream cout ("ctc.out") ;

vector<int> v[100009], invers[100009] ;

int n, frecv[100009] ;

deque<int> dq ;

void fil(int nod)
{
    if(frecv[nod])return ;

    frecv[nod] = 1 ;

    for(int f = 0 ; f < v[nod].size() ; f ++)
        fil(v[nod][f]) ;

    dq.push_back(nod) ;
}

vector<vector<int> > rez ;

vector<int> aux ;

void fil2(int nod)
{
    if(frecv[nod])return ;

    frecv[nod] = 1 ;

    for(int f = 0 ; f < invers[nod].size() ; f ++)
        fil2(invers[nod][f]) ;

    aux.push_back(nod) ;
}

int main()
{
    int q ;

    cin >> n >> q ;

    while(q --)
    {
        int a, b ;

        cin >> a >> b ;

        v[a].push_back(b) ;

        invers[b].push_back(a) ;
    }

    for(int f = 1 ; f <= n ; f ++)
        if(!frecv[f])fil(f) ;

    /// inversam graful

    for(int f = 1 ; f <= n ; f ++)
        frecv[f] = 0 ;

    while(dq.size())
    {
        int nod = dq.back() ;

        if(frecv[nod])dq.pop_back() ;
        else
        {
            fil2(nod) ;

            rez.push_back(aux) ;

            aux.clear() ;
        }
    }

    cout << rez.size() << endl ;

    for(int f = 0 ; f < rez.size() ; f ++)
    {
        for(int e = 0 ; e < rez[f].size() ; e ++)
            cout << rez[f][e] << " " ;

        cout << '\n' ;
    }
    return 0 ;
}