Cod sursa(job #2648060)

Utilizator horia_mercanHoria Mercan horia_mercan Data 8 septembrie 2020 15:32:09
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.47 kb
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
#define  NMAX 100002

using namespace std;

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

vector<int> G[NMAX] , GT[NMAX] , CTC[NMAX];
int member_of_CTC[NMAX] , nr_CTC = 0;
int viz[NMAX];
stack <int> s;

int n , m;
void dfs1(int nod){
    viz[nod] = 1;
    int size_ = G[nod].size();
    int vecin ;
  //  sort(G[nod].begin() , G[nod].end());
    for(int i = 0 ; i<size_ ; i++){
        vecin = G[nod][i];
        if(viz[vecin] == 0){
            dfs1(vecin);
        }
    }
    s.push(nod);
}
void dfs2(int nod){
    int  vecin , size_ = GT[nod].size();
    CTC[nr_CTC].push_back(nod);
    member_of_CTC[nod] = nr_CTC;
    viz[nod] = 2;
    for(int i=0 ; i<size_ ; i++){
        vecin = GT[nod][i];
        if(viz[vecin] == 1)
            dfs2(vecin);
    }
}
int main()
{
    cin>>n>>m;
    int x , y , nod;
    while(m--){
        cin>>x>>y;
        G[x].push_back(y);
        GT[y].push_back(x);
    }
    for(int i = 1 ; i<=n ; i++){
        if(!viz[i]) dfs1(i);
    }

    while(!s.empty()){
        nod = s.top();
        //cout<<nod<<endl;
       if(viz[nod]==1){
            nr_CTC ++;
            dfs2(nod);
        }
        s.pop();
    }
    cout<<nr_CTC<<'\n';
    for(int i  = 1 ; i<=nr_CTC ; i++){
        for(int j = 0 ; j< CTC[i].size() ; j++){
            cout<<CTC[i][j]<<' ';
        }
        cout<<'\n';
    }
    return 0;
}