Cod sursa(job #3331813)

Utilizator bezea.andrei20Bezea Andrei bezea.andrei20 Data 31 decembrie 2025 14:53:20
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.93 kb
#include <fstream>
#include <queue>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <map>
#include <unordered_map>
#include <string>
#include <unordered_set>
#include <set>
#include <stack>
#include <climits>
#include <iomanip>
#include <bitset>
using namespace std;

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

const int NMAX = 1e5+5;
const int MOD = 1e9+7;
const int INF = (1 << 30);

using ld = long double;
using ull = unsigned long long;
using ll = long long;
using ui = unsigned int;
using pii = pair<int, int>;

int n,m,t,indEdges,indBcc;
vector<int> graf[NMAX];
int low[NMAX];
int dfsTime[NMAX];
pii edges[NMAX];
unordered_set<int> bcc[NMAX];

void GetBCC(pii rootEdge) {
    indBcc++;
    while (edges[indEdges]!=rootEdge) {
        bcc[indBcc].insert(edges[indEdges].first);
        bcc[indBcc].insert(edges[indEdges].second);
        indEdges--;
    }
    bcc[indBcc].insert(edges[indEdges].first);
    bcc[indBcc].insert(edges[indEdges].second);
    indEdges--;
}

void dfs(int node,int dad) {
    dfsTime[node]=low[node]=++t;

    for (auto &vecin:graf[node]) {
        if (vecin!=dad && dfsTime[vecin]<dfsTime[node]) {
            edges[++indEdges]={node,vecin};
        }
        if (!low[vecin]) {
            dfs(vecin,node);
            low[node]=min(low[node],low[vecin]);
            if (low[vecin]>=dfsTime[node]) GetBCC({node,vecin});
        }
        else if (vecin!=dad) low[node]=min(low[node],dfsTime[vecin]);
    }
}

void solve() {
    cin>>n>>m;
    for (int i=1;i<=m;i++) {
        int x,y;
        cin>>x>>y;
        graf[x].push_back(y);
        graf[y].push_back(x);
    }

    for (int i=1;i<=n;i++) {
        if (!low[i]) dfs(i,0);
    }

    cout<<indBcc<<"\n";
    for (int i=1;i<=indBcc;i++,cout<<"\n") {
        for (auto &node:bcc[i]) cout<<node<<" ";
    }
}

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

    solve();
    return 0;
}