Cod sursa(job #2816092)

Utilizator raduandreiRadu Andrei raduandrei Data 11 decembrie 2021 00:24:41
Problema Componente tare conexe Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.96 kb
#include <iostream>
#include <bits/stdc++.h>

using namespace std;

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

class Graf {
    int nr_noduri, nr_muchii;
    vector<int> muchii[10005];
    vector<int> muchii_graf_transpus[10005];
    vector<int> CTC[10005];
    queue<int> coada;
    int vizitat[10005] = {};

    int timp = 0;
    int nr_ctc = 0;
    stack<int> s;
public:

    //citirea din fisier a muchiilor
    void citire() {
        int x, y;
        in >> nr_noduri;
        in >> nr_muchii;
        for (int i = 1; i <= nr_muchii; ++i) {
            in >> x >> y;
            muchii[x].push_back(y);
            //muchii[y].push_back(x);

            //adaugare pentru construirea grafului transpus
            muchii_graf_transpus[y].push_back(x);
        }
    }

    //parcurgere in adancime
    void dfs(int x){
        vizitat[x] = 1;
        for(auto val : muchii[x])
            if(!vizitat[val])
                dfs(val);
            //adaugare varfuri in stiva dupa momentul terminarii vizitarii acestora
            s.push(x);
        }

        //parcurgere in adancime graf transpus
        //fara paramentru deoarece adaugam noduri din stiva
    void dfs_graf_transpus(int x){
                vizitat[x] = 2;
                CTC[nr_ctc].push_back(x);
                for(auto val : muchii_graf_transpus[x])
                    if(vizitat[val] != 2)
                        dfs_graf_transpus(val);
    }

    void kosaraju(){
        Graf::citire();
        for(int i = 1; i <= nr_noduri; ++i)
            if(!vizitat[i])
                Graf::dfs(i);
        while(s.size()) {
            int x = s.top();

            if(vizitat[x] != 2)
                ++nr_ctc,dfs_graf_transpus(x);

            s.pop();

        }
      out << nr_ctc << endl;
        for(int i = 1; i <= nr_ctc; ++i){
            for(auto val : CTC[i])
                out << val << " ";
            out << endl;
        }
    }

    };

    int main() {

    Graf G;
    G.kosaraju();
        return 0;
    }