Cod sursa(job #2139091)

Utilizator RazvanR104Razvan-Andrei Ciocoiu RazvanR104 Data 22 februarie 2018 01:56:31
Problema Componente biconexe Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 kb
#include <bits/stdc++.h>

using namespace std;

const int NMAX = 100010;
const int inf = 0x3f3f3f3f;

int N, M;
int currTime = 0;
int discoverTime[NMAX], lowLink[NMAX];
vector<int> G[NMAX];
vector<vector<int>> BCC;
vector<pair<int, int>> tarjanEdges;

void tarjanDFS(int node, int from) {
	discoverTime[node] = currTime++;
	for (int it: G[node]) {
		if (it == from)
			continue;
		if (discoverTime[it] != -1) {
			lowLink[node] = min(lowLink[node], discoverTime[it]);
			continue;
		}
		tarjanEdges.push_back({node, it});
		tarjanDFS(it, node);
		lowLink[node] = min(lowLink[node], lowLink[it]);
		if (lowLink[it] >= discoverTime[node]) {
			vector<int> currBcc;
			int x, y;
			do {
				tie(x, y) = tarjanEdges.back();
				tarjanEdges.pop_back();
				currBcc.push_back(x);
				currBcc.push_back(y);
			} while (x != node || y != it);
			sort(currBcc.begin(), currBcc.end());
			currBcc.erase(unique(currBcc.begin(), currBcc.end()), currBcc.end());
			BCC.push_back(currBcc);
		}
	}
}

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

	memset(discoverTime, -1, sizeof discoverTime);
	memset(lowLink, inf, sizeof lowLink);

	cin >> N >> M;
	while (M--) {
		int x, y;
		cin >> x >> y;
		G[x].push_back(y);
		G[y].push_back(x);
	}

	tarjanDFS(1, 0);
	cout << BCC.size() << '\n';
	for (auto i: BCC) {
		for (auto j: i)
			cout << j << ' ';
		cout << '\n';
	}

	return 0;
}