Cod sursa(job #3005018)

Utilizator bogdanvladmihaiBogdan Vlad-Mihai bogdanvladmihai Data 16 martie 2023 18:54:06
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.29 kb
#include <bits/stdc++.h>
using namespace std;

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

const int MAXN = 1e5;

struct Edge {
    int u, v;
};

int N, M;
int cnt, compCount;
int desc[MAXN + 1], low[MAXN + 1];
int fr[MAXN + 1];
bool visited[MAXN + 1];
vector<int> G[MAXN + 1];
vector<int> compNodes[MAXN + 1];

int top;
Edge edges[2 * MAXN + 1];

// Vom vrea sa tinem o "stiva" care sa retina muchiile parcurse (in ordine)

void removeEdges(Edge e) {
    while (top > 0 && !(edges[top - 1].u == e.u && edges[top - 1].v == e.v)) {
        compNodes[compCount].push_back(edges[top - 1].u);
        compNodes[compCount].push_back(edges[top - 1].v);
        top--;
    }
    compNodes[compCount].push_back(edges[top - 1].u);
    compNodes[compCount].push_back(edges[top - 1].v);
    top--;
    compCount++;
}

void dfs(int u) {
    visited[u] = true;
    desc[u] = low[u] = cnt++;
    for (int v : G[u]) {
        if (!visited[v]) {
            Edge e;
            e.u = u;
            e.v = v;
            edges[top++] = e;
            dfs(v);
            low[u] = min(low[u], low[v]);
            if (desc[u] <= low[v]) {
                // Avem un punct de articulatie
                // Stim ca pe muchai u -> v ne-am dus in jos si nu ne-am putut intoarce undeva mai sus decat u
                // Atunci, vrem sa scoatem din lista de muchii toate muchiile parcurse dupa muchia u -> v
                // Atunci stim ca toate nodurile care apartin muchiilor scoate sunt intr-o comp conexa. 
                removeEdges(e);
            }
        } else {
            low[u] = min(low[u], desc[v]);
        }
    }
}

int main() {
    in >> N >> M;
    for (int i = 0; i < M; i++) {
        int u, v; in >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }

    for (int i = 1; i <= N; i++) {
        if (!visited[i]) {
            dfs(i);
        }
    }

    out << compCount << "\n";
    for (int i = 0; i < compCount; i++) {
        vector<int> nodeList;
        for (int node : compNodes[i]) {
            fr[node]++;
            if (fr[node] == 1) {
                nodeList.push_back(node);
            }
        }
        for (int node : compNodes[i]) {
            fr[node]--;
        }
        for (int node : nodeList) {
            out << node << " ";
        }
        out << "\n";
    }
    return 0;
}