Cod sursa(job #3203025)

Utilizator AndreiDeltaBalanici Andrei Daniel AndreiDelta Data 12 februarie 2024 22:36:42
Problema Componente biconexe Scor 46
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.89 kb
#include <deque>
#include <algorithm>
#include <vector>
#include <fstream>
#include <iostream>
#include <stack>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#define pb push_back
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
typedef long long ll;
typedef pair<int, int> pi;
int t, T;

void DFS(int nod, int depth, vector<vector<int>>& V, 
        stack<int>& S, vector<int>& dp, vector<int>& lvl, vector<int>& viz, vector<vector<int>>& comp) {
    viz[nod] = 1;
    lvl[nod] = depth;
    dp[nod] = depth;
    S.push(nod);

    for (int neigh : V[nod]) {
        if (viz[neigh] == 1) {
            dp[nod] = min(dp[nod], lvl[neigh]);
        }
        else 
        if(viz[neigh] == 0){
            DFS(neigh, depth + 1, V, S, dp, lvl, viz, comp);
            dp[nod] = min(dp[nod], dp[neigh]);

            if (dp[neigh] >= lvl[nod]) { // the edge from the child and its parent (the current node) is a bridge
                vector<int> ans;
                while (S.top() != nod) {
                    ans.push_back(S.top());
                    S.pop();
                }
                ans.push_back(nod);
                comp.push_back(ans);
            }
        }
    }

    viz[nod] = 2;
}


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    f >> n >> m;
    vector<vector<int>> V(n + 1);
    for (int i = 0; i < m; i++) {
        int a, b;
        f >> a >> b;
        V[a].push_back(b);
        V[b].push_back(a);
    }

    stack<int> S;
    vector<int> dp(n + 1, 0), lvl(n + 1, 0), viz(n + 1, 0);
    vector<vector<int>> comp;

    DFS(1, 0, V, S, dp, lvl, viz, comp);

    g << comp.size() << '\n';
    for (vector<int>& ans : comp) {
        for (int x : ans) g << x << ' ';
        g << '\n';
    }

    return 0;
}