Cod sursa(job #2713825)

Utilizator MateGMGozner Mate MateGM Data 28 februarie 2021 18:23:26
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.22 kb
#include <iostream>
#include <vector>
#include <stack>
#include <fstream>

using namespace std;

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

void beolvas(vector<vector<int>>& graf, int n, int m);
void tarjan(vector<vector<int>>& graf, int n);
void dfs_scc(vector<vector<int>>& graf, vector<int>& belep, vector<bool>& vermen, vector<int> &low, stack<int> &verem, vector<vector<int>> &komponensek, int &komponens, int &ido, int v);

int main(){
    int n, m;
    be >> n >> m;
    vector<vector<int>> graf(n); 
    beolvas(graf, n, m);
    tarjan(graf, n);
}

void beolvas(vector<vector<int>>& graf, int n, int m) {
    for (int i = 0; i < m; i++) {
        int x, y;
        be >> x >> y;
        graf[x - 1].push_back(y - 1);
    }
}

void tarjan(vector<vector<int>>& graf, int n) {
    vector<int> belep(n, -1);
    vector<bool> vermen(n, false);
    vector<int> low(n, -1);
    stack<int> verem;
    vector<vector<int>> komponensek;

    int ido = 0;
    int v = 0;
    int komponens = 0;
    dfs_scc(graf, belep, vermen, low, verem, komponensek, komponens, ido, v);

    ki << komponens << endl;
    for (int i = komponensek.size()-1; i >=0 ; i--) {
        for (int j = komponensek[i].size() - 1; j >= 0; j--)
            ki << komponensek[i][j] + 1 << " ";
        ki << endl;
    }

}


void dfs_scc(vector<vector<int>>& graf, vector<int>& belep, vector<bool>& vermen, vector<int>& low, stack<int>& verem, vector<vector<int>>& komponensek, int& komponens, int& ido, int v) {
    ido++;
    belep[v] = ido;
    low[v] = ido;
    vermen[v] = true;
    verem.push(v);

    for (int i : graf[v]) {
        if (belep[i] == -1) {
            dfs_scc(graf, belep, vermen, low, verem, komponensek, komponens, ido, i);
            low[v] = min(low[v], low[i]);
        }
        else if ((belep[i] < belep[v]) && vermen[i]) {
            low[v] = min(low[v], belep[i]);
        }
    }

    if (low[v] == belep[v]) {
        komponens++;
        komponensek.resize(komponens);
        while (!verem.empty() && (belep[verem.top()] >= belep[v])) {
            komponensek[komponens - 1].push_back(verem.top());
            vermen[verem.top()] = false;
            verem.pop();
        }
    }
}