Cod sursa(job #2792084)

Utilizator Tudor_IlieIlie Tudor Tudor_Ilie Data 31 octombrie 2021 20:47:08
Problema Componente tare conexe Scor 18
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.63 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;

ifstream in("ctc.in");
ofstream out("ctc.out");
vector<vector<int>> Componente;
int timeG = 1;
struct GraphTimeStamps{
    int entert = -1;
    int leavet = -1;
    int low_link = -1;
};

void dfs(int node, vector<int>* G, GraphTimeStamps* GTS, stack<int>& s, bool* onStack ){
    s.push(node);
    onStack[node] = true;
    GTS[node].low_link = timeG;
    GTS[node].entert = GTS[node].low_link;
    timeG++;
    for(auto vecin:G[node]){
        if(GTS[vecin].entert==-1){ // inseamna ca vecinul respectiv nu e vizitat
//            cout<<"vizitam "<<vecin<<endl;
            dfs(vecin, G, GTS,s,onStack);
//            cout<<"am terminat de vizitat "<<vecin<<endl;
            GTS[node].low_link = min(GTS[node].low_link,GTS[vecin].low_link);
        }
        else if(onStack[vecin]){ // inseamna ca vecinul este pe stiva deci face parte din aceeasi componenta conexa
//            cout<<"nu mai vizitam "<<vecin<<"pentru ca este deja pe stiva \n";
            GTS[node].low_link = min(GTS[node].low_link,GTS[vecin].entert);
        }

    }
    GTS[node].leavet = timeG++;
    if(GTS[node].entert == GTS[node].low_link){
        vector<int> temp;
        while(s.top()!=node){
            temp.push_back(s.top()+1);
            int topElem = s.top();
            onStack[topElem] = false;
            GTS[topElem].low_link = GTS[node].low_link;
            s.pop();
        }
        temp.push_back(s.top()+1);
        int topElem = s.top();
        onStack[topElem] = false;
        s.pop();
        Componente.push_back(temp);
    }
}


int main(){


    int n,m;
    in>>n>>m;
    vector<int> G[n];
    GraphTimeStamps GTS[n];
    stack<int> s;
    bool onStack[n]{(false)};

    for(int i = 0;i<m;i++){
        int x,y;
        in>>x>>y;
        G[x-1].push_back(y-1);
    }
//    afisare listei de adiacenta
//    for(int i = 0;i<n;i++){
//        cout<<i<<" : ";
//        for(auto node:G[i]){
//            cout<<node<<" ";
//        }
//        cout<<endl;
//    }
    for(int i=0;i<n;i++){
        if(GTS[i].entert == -1){
            dfs(0,G,GTS,s,onStack);
        }
    }
    out<<Componente.size()<<'\n';
    for(auto cc:Componente){
        for(auto node:cc){
            out<<node<<" ";
        }
        out<<'\n';
    }
//    for(auto elem : GTS){
//        cout<<elem.entert<<" ";
//
//    }
//    cout<<endl;
//    for(auto elem : GTS){
//        cout<<elem.leavet<<" ";
//    }
//
//    cout<<endl;
//    for(auto elem : GTS){
//        cout<<elem.low_link<<" ";
//    }
}