Cod sursa(job #1910228)

Utilizator lflorin29Florin Laiu lflorin29 Data 7 martie 2017 16:05:09
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.49 kb
#include <bits/stdc++.h>

using namespace std;

const int nMax = 1e5 + 2;

int n, m, low[nMax], in[nMax];
vector<int>g[nMax];
vector<vector<int>>comp;
stack<pair<int, int>>st;

void Citire() {
	scanf("%d%d", &n, &m);

	for (int i = 1, x, y; i <= m; ++i) {
		scanf("%d%d", &x, &y);
		g[x].push_back(y), g[y].push_back(x);
	}
}

void add_comp(int nod, int fiu) {
	comp.push_back(vector<int>());
	int a, b;
	do {
		a = st.top().first;
		b = st.top().second;
		st.pop();
		comp.back().push_back(a);
		comp.back().push_back(b);
	}
	while (a != nod or b != fiu);
}

void tarjan(int nod, int father, int level = 1) {
	in[nod] = level;
	low[nod] = level;

	for (const auto& fiu : g[nod]) {
		if (fiu == father)
			continue;

		if (!in[fiu]) {
			st.emplace(nod, fiu);
			tarjan(fiu, nod, level + 1);
			low[nod] = min(low[nod], low[fiu]);
			if (low[fiu] >= level) {
				add_comp(nod, fiu);
			}
		}
		else {
			low[nod] = min(low[nod], in[fiu]);
		}
	}
}

void make_unique(vector<int>&that) {
	sort(that.begin(), that.end());
	that.resize(unique(that.begin(), that.end()) - that.begin());
}

void print(const vector<int>&that) {
	for (const auto& itr : that)
		printf("%d ", itr);

	printf("\n");
}

void PrintComps() {
	printf("%d\n", comp.size());

	for (auto& itr : comp) {
		make_unique(itr);
		print(itr);
	}
}

int main() {
	freopen("biconex.in", "r", stdin);
	freopen("biconex.out", "w", stdout);

	Citire();
	tarjan(1, 0, 1);
	PrintComps();
}