Cod sursa(job #2667400)

Utilizator STEFAN-ZOTAZota Stefan-Daniel STEFAN-ZOTA Data 3 noiembrie 2020 13:41:03
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.67 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <string.h>

using namespace std;

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

int n, m, x, y, vizitat[100001], low[100001], vf;
vector <int> G[100001], aux;
vector <vector <int>> rez;
pair <int, int> stiva[200001];

void citire() {
    f >> n >> m;
    for(int i = 1; i <= m; i++) {
        f >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
}

void biconex(int lx, int ly) {
    aux.clear();
    x = stiva[vf].first;
    y = stiva[vf].second;
    vf--;
    aux.push_back(y);
    while(lx != x && ly != y){
        x = stiva[vf].first;
        y = stiva[vf].second;
        vf--;
        aux.push_back(y);
    }
    aux.push_back(x);
    rez.push_back(aux);
}

void DFS(int node, int tata, int nr) {
    vizitat[node] = nr;
    low[node] = nr;
    for(int i = 0; i < G[node].size(); i++) {
        if(G[node][i] != tata) {
            if(vizitat[G[node][i]] == -1) {
                vf++;
                stiva[vf] = make_pair(node, G[node][i]);
                DFS(G[node][i], node, nr + 1);
                low[node] = min(low[node], low[G[node][i]]);
                if(low[G[node][i]] >= vizitat[node])
                    biconex(node, G[node][i]);
            }else {
                low[node] = min(low[node], vizitat[G[node][i]]);
            }
        }
    }
}

int main() {
    citire();
    memset(vizitat, -1, sizeof(vizitat));
    DFS(1, 0, 0);
    g << rez.size() << '\n';
    for(int i = 0; i < rez.size(); i++) {
        for(int j = 0; j < rez[i].size(); j++)
            g << rez[i][j] << ' ';
        g << '\n';
    }
}