Cod sursa(job #2932046)

Utilizator MihaiZ777MihaiZ MihaiZ777 Data 1 noiembrie 2022 18:37:42
Problema Componente biconexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.46 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];

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]) {
            fout << chain.size() << '\n';
            
            while (!chain.empty() && chain.back() != node) {
                fout << chain.back() << ' ';
                chain.pop_back();
            }
            fout << node << ' ';
            fout << '\n';
        }
    }
}

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);
    }
}