Cod sursa(job #2576508)

Utilizator dahaandreiDaha Andrei Codrin dahaandrei Data 6 martie 2020 20:02:14
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.34 kb
#include <bits/stdc++.h>

using namespace std;

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

const int MAXN = 1e5;
const int MAXM = 2e5;

int n, m;
vector<int> g[MAXN + 1];
int lvl[MAXN + 1], minn[MAXN + 1];
vector<int> bico[MAXN + 1];
int cnt;
stack<pair<int, int> > edges;

void dfs(int nod, int boss) {
	lvl[nod] = minn[nod] = lvl[boss] + 1;
	for (auto &x : g[nod]) {
		if (x == boss) continue;
		if (lvl[x]) minn[nod] = min(minn[nod], lvl[x]);
		else {
			edges.push({nod, x});
			dfs(x, nod);
			if (minn[x] >= lvl[nod]) {
				++ cnt;
				pair<int, int> cur;
				do {
					cur = edges.top();
					edges.pop();
					bico[cnt].push_back(cur.first);
					bico[cnt].push_back(cur.second);
				} while ((cur.first != x || cur.second != nod) && (cur.first != nod || cur.second != x));
				sort(bico[cnt].begin(), bico[cnt].end());
				bico[cnt].erase(unique(bico[cnt].begin(), bico[cnt].end()), bico[cnt].end());
			}
			minn[nod] = min(minn[nod], minn[x]);
		}
	}
}

int main() {
	in >> n >> m;
	for (int i = 1; i <= m; ++ i) {
		int a, b;
		in >> a >> b;
		g[a].push_back(b);
		g[b].push_back(a);
	}

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

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

	return 0;
}