Cod sursa(job #2925281)

Utilizator matei123Biciusca Matei matei123 Data 13 octombrie 2022 13:36:35
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.51 kb
#include <bits/stdc++.h>

#include <utility>

using namespace std;

class Graph {
private:
    vector<vector<int>> gr;
    int n;
    vector<int> viz; ///vector de vizitati pentru graf

public:
    Graph(vector<vector<int>> gr_, int n_) : gr(std::move(gr_)), n(n_) {
        viz.resize(n + 1, 0); ///initializarea vectorului
    }
    ///implementarea algoritmului lui Tarjan
    ///folosind recursivitate de tip DFS
    void Tarjan(int node, int& level, vector<int>& initialLevel, vector<int>& minLevel,
             stack<int>& st, vector<bool>& isInStack,
             vector<vector<int>>& ctc) {
        if(minLevel[node] >= 0){
            return;
        }
        level += 1; ///trecerea la urmatorul nivel al grafului
        initialLevel[node] = level;
        minLevel[node] = level;
        st.push(node); ///punerea in stiva

        isInStack[node] = true;
        for(int child: gr[node]){
            Tarjan(child, level, initialLevel, minLevel, st, isInStack, ctc);
            ///parcurgerea grafului orientat cu DFS pt Tarjan
            if(isInStack[child]){
                minLevel[node] = min(minLevel[node], minLevel[child]);
            }
        }

        if(initialLevel[node] == minLevel[node]){
            ctc.push_back({}); ///am gasit un nou CTC
            int x = -1;
            do{
                x = st.top();
                st.pop();
                isInStack[x] = false;
                ctc.back().push_back(x);
            }while(x != node);
        }
    }
};

int main() {
    ifstream f("ctc.in");
    ofstream g("ctc.out");
    int n, m;
    ///implementarea citirii
    f >> n >> m;

    vector<vector<int>> gr(n + 1);
    for(int x, y, i = 1; i <= m; i++) {
        f >> x >> y;
        gr[x].push_back(y);
    }
    ///crearea obiectului de tip Graph
    Graph grf(gr, n);

    int level = 0;
    vector<int> initialLevel(n + 1, -1);
    vector<int> minLevel(n + 1, -1);
    stack<int> st;
    vector<bool> isInStack(n + 1, false);
    vector<vector<int>> ctc;
    ///declarea structurilor de date necesare
    ///pt rezolvarea problemei cu Tarjan

    for(int node = 1; node <= n; ++node){
        if(minLevel[node] < 0){
            grf.Tarjan(node, level, initialLevel, minLevel, st, isInStack, ctc);
        }
    }

    ///afisarea
    g << ctc.size() << "\n";
    for(vector<int>& nodes: ctc){
        for(int node: nodes){
            g << node << " ";
        }
        g << "\n";
    }

    g.close();
    return 0;
}