Cod sursa(job #2932053)

Utilizator MihaiZ777MihaiZ MihaiZ777 Data 1 noiembrie 2022 19:01:40
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.73 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <math.h>
using namespace std;

ifstream fin("biconex.in");
ofstream fout("biconex.out");

int n, m;
vector <int> graph[100005];
bool visited[100005];
vector <int> chain;
int highestLevel[100005];
int level[100005];
vector <vector <int>> biconex;

void DFS(int node, int parent) {
    visited[node] = true;
    level[node] = level[parent] + 1;
    highestLevel[node] = level[node];
    chain.push_back(node);

    for (int newNode : graph[node]) {
        if (newNode == parent) {
            continue;
        }
        if (visited[newNode]) {
            highestLevel[node] = min(highestLevel[node], level[newNode]);
            continue;
        }

        DFS(newNode, node);
        highestLevel[node] = min(highestLevel[node], highestLevel[newNode]);

        if (highestLevel[newNode] >= level[node]) {

            vector <int> temp;
            
            while (!chain.empty() && chain.back() != newNode) {
                temp.push_back(chain.back());
                chain.pop_back();
            }
            temp.push_back(newNode);
            chain.pop_back();
            temp.push_back(node);
            biconex.push_back(temp);
        }
    }
}

int main() {
    fin >> n >> m;
    for (int i = 0; i < m; i++) {
        int a, b;
        fin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    for (int i = 1; i <= n; i++) {
        if (visited[i]) {
            continue;
        }

        DFS(i, 0);
    }

    fout << biconex.size() << '\n';
    for (auto x : biconex) {
        for (auto y : x) {
            fout << y << ' ';
        }
        fout << '\n';
    }
}