Cod sursa(job #2927040)

Utilizator tiberiusss26Titiriga Tiberiu Nicolae tiberiusss26 Data 19 octombrie 2022 11:01:36
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.64 kb
#include <iostream>
#include <vector>
#include <stack>
#include <fstream>

using namespace std;

int n, k=0;
vector<vector<int>> solutie;


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

struct vertex {
    int index = -1;
    int lowlink = -1;
    bool peStiva = false;
};

void tareConex(int nod, int &ind, stack<int> &stiv, vertex v[n + 1], vector<vector<int>> &listaAdiacenta) {
    v[nod].index = ind;
    v[nod].lowlink = ind;
    ind++;
    stiv.push(nod);
    v[nod].peStiva = true;

    for (auto vec: listaAdiacenta[nod]) {
        if (v[vec].index == -1) {
            tareConex(vec, ind, stiv, v, listaAdiacenta);
            v[nod].lowlink = min(v[nod].lowlink, v[vec].lowlink);
        } else if (v[vec].peStiva)
            v[nod].lowlink = min(v[nod].lowlink, v[vec].index);
    }

    if (v[nod].lowlink == v[nod].index) {
        k++;
        vector<int> sol;
        int w;
        do {
            w = stiv.top();
            stiv.pop();
            v[w].peStiva = false;
            sol.push_back(w);
        }while(w!=nod);
        solutie.push_back(sol);
    }
}

void tarjan() {
    int index = 0, m, x, y;
    stack<int> stiva;
    f >> n >> m;
    vector<vector<int>> listaAd(n + 1);
    for (int i = 0; i < m; i++) {
        f >> x >> y;
        listaAd[x].push_back(y);
    }
    f.close();
    vertex v[n + 1];
    for (int i = 1; i <= n; i++) {
        if (v[i].index == -1)
            tareConex(i, index, stiva, v, listaAd);
    }
}

int main() {
    tarjan();
    g<<k<<"\n";
    for(auto &it: solutie)
        std::sort(it.begin(), it.end());
    for(auto it: solutie)
    {
        for(auto nod: it)
            g<<nod<<" ";
        g<<"\n";
    }
}