Cod sursa(job #2413568)

Utilizator LucaSeriSeritan Luca LucaSeri Data 23 aprilie 2019 15:36:10
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.35 kb
#include <bits/stdc++.h>
 
using namespace std;

#define all(x) (x).begin(), (x).end()
const int MAXN = 1e5 + 10;

vector< int > gr[MAXN];
int lvl[MAXN], minn[MAXN];

stack< pair< int, int > > edges;
vector< int > bico[MAXN];

int cnt = 0;

void dfs(int node, int boss) {
	lvl[node] = minn[node] = lvl[boss] + 1;

	for(auto &x : gr[node]) {
		if(x == boss) continue;
		if(lvl[x]) minn[node] = min(minn[node], lvl[x]);
		else {
			edges.push({node, x});
			dfs(x, node);
			if(minn[x] >= lvl[node]) {
				int a, b;
				++cnt;
				do {
					tie(a, b) = edges.top();
					edges.pop();
					bico[cnt].emplace_back(a);
					bico[cnt].emplace_back(b);
				} while(a != node || b != x);

				sort(all(bico[cnt]));
				bico[cnt].erase(unique(all(bico[cnt])), bico[cnt].end());
			}

			minn[node] = min(minn[node], minn[x]);
		}
	}
}
int main() {
	#ifdef BLAT
		freopen("input", "r", stdin);
	#else
		freopen("biconex.in", "r", stdin);
		freopen("biconex.out", "w", stdout);
	#endif
 
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	srand(time(nullptr));

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

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

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

	cout << cnt << '\n';
	for(int i = 1; i <= cnt; ++i) {
		for(auto &x : bico[i]) cout << x << ' ';
			cout << '\n';
	}
	return 0;
}