Cod sursa(job #3181203)

Utilizator maiaauUngureanu Maia maiaau Data 6 decembrie 2023 17:27:31
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.16 kb
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
#define fi first 
#define se second
#define pb push_back

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

const int N = 1e5+3;

int n, k, niv[N], low[N];
bitset<N> u;
stack<pii> stk;
vector<vector<int>> e, comp;

void read(), dfs(int, int, int), addcomp(int,int);

int main()
{
    read();
	dfs(1, 0, 1);
	g << k << '\n';
	for (int i = 0; i < k; i++){
		for (auto it: comp[i]) g << it << ' ';
		g << '\n';
	}

    return 0;
}

void read(){
    int m; f >> n >> m;
	e.resize(n+2);
	while (m--){
		int a, b; f >> a >> b;
		e[a].pb(b); e[b].pb(a);
	}
}
void dfs(int nod, int t, int h){
	u[nod] = 1; 
	int cnt = 0; 
	niv[nod] = low[nod] = h;
	for (auto it: e[nod]){
		if (it == t) continue;
		if (u[it]) {
			low[nod] = min(low[nod], niv[it]); 
			continue;
		}
		stk.push({nod, it});
		dfs(it, nod, h+1);
		low[nod] = min(low[nod], low[it]);
		if (low[it] >= niv[nod])
			addcomp(nod, it);

	}
}
void addcomp(int a, int b){
	unordered_set<int> s;
	comp.pb({});
	int x, y;
	do {
		tie(x, y) = stk.top(); stk.pop();
		s.insert(x); s.insert(y);
	} while (x != a || y != b);
	for (auto it: s)
		comp[k].pb(it);
	k++;
}