Cod sursa(job #2791685)

Utilizator GasparAndreiGaspar Andrei GasparAndrei Data 30 octombrie 2021 22:14:38
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.09 kb
#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;

//ifstream cin("qclasa.in");
//ofstream cout("qclasa.out");

vector <int> G[100005],GT[100005];
stack <int> S;
vector<int> result[100005];

int n,m,x,y;
int v[100005];
int nrctc;

void DFS_T(int nod){
    v[nod]=2;
    result[nrctc].push_back(nod);
    for(auto i:GT[nod]){
        if(v[i]==1)
            DFS_T(i);
    }
}

void dfs(int nod){

    v[nod]=1;
    for(auto i:G[nod]){
        if(!v[i])
            dfs(i);
    }
    S.push(nod);

}

int main()
{
    cin >> n >> m;
    while(cin>>x>>y)
        G[x].push_back(y),GT[y].push_back(x);
    
    for(int i=1;i<=n;++i){
        if(!v[i])
            dfs(i);
    }
    while(!S.empty()){
        int Nod=S.top();
        if(v[Nod]==1){
            nrctc++;
            DFS_T(Nod);
        }
        S.pop();
    }
    cout << nrctc << '\n';
    for(int i=1;i<=nrctc;++i){
        for(auto j:result[i]){
            cout << j << ' ';
        }
        cout << '\n';
    }
    

    return 0;
}