Cod sursa(job #2335418)

Utilizator LucaSeriSeritan Luca LucaSeri Data 4 februarie 2019 07:59:35
Problema Componente biconexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.35 kb
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e5 + 10;

vector< int > gr[MAXN];
int minim[MAXN], level[MAXN];
stack< pair< int, int > > edges;
int cntBiconexe = 0;

vector< int > sol[MAXN];

void get(int x, int y) {
	int nowX = 0, nowY = 0;
	do{
		tie(nowX, nowY) = edges.top();
		edges.pop();

		sol[cntBiconexe].emplace_back(nowX);
		sol[cntBiconexe].emplace_back(nowY);
	} while(nowX != x || nowY != y);

	sort(sol[cntBiconexe].begin(), sol[cntBiconexe].end());
	sol[cntBiconexe].erase(unique(sol[cntBiconexe].begin(), sol[cntBiconexe].end()), sol[cntBiconexe].end());

	++cntBiconexe; 
}

void dfs(int node, int d) {
	minim[node] = level[node] = d;
	for(auto &x : gr[node]) {
		if(!level[x]) {
			edges.push(make_pair(node, x));
			dfs(x, d + 1);
			if(minim[x] >= level[node]) {
				get(node, x);
			}

			minim[node] = min(minim[node], minim[x]);
		} else minim[node] = min(minim[node], level[x]);
	}
}


int main() {
	#ifdef BLAT
		freopen("input", "r", stdin);
	#else
		freopen("biconex.in", "r", stdin);
		freopen("biconex.out", "w", stdout);
	#endif

	int n, m;
	cin >> n >> m;

	for(int i = 0; i < m; ++i) {
		int a, b;
		cin >> a >> b;
		gr[a].emplace_back(b);
		gr[b].emplace_back(a);
	}


	dfs(1, 1);

	cout << cntBiconexe << '\n';
	for(int i = 0; i < cntBiconexe; ++i) {
		for(auto &x : sol[i]) {
			cout << x << ' ';
		}

		cout << '\n';
	}
}