Cod sursa(job #2139075)

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

using namespace std;

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

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

void tarjanDFS(int node) {
	discoverTime[node] = currTime++;
	for (int it: G[node]) {
		if (discoverTime[it] != -1) {
			lowLink[node] = min(lowLink[node], discoverTime[it]);
			continue;
		}
		tarjanEdges.push({node, it});
		tarjanDFS(it);
		lowLink[node] = min(lowLink[node], lowLink[it]);
		if (lowLink[it] >= discoverTime[node]) {
			int x, y;
			do {
				tie(x, y) = tarjanEdges.top();
				tarjanEdges.pop();
				BCC[currBcc].push_back(x);
				BCC[currBcc].push_back(y);
			} while (x != node || y != it);
			sort(BCC[currBcc].begin(), BCC[currBcc].end());
			BCC[currBcc].erase(unique(BCC[currBcc].begin(), BCC[currBcc].end()), BCC[currBcc].end());
			++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);
	cout << currBcc << '\n';
	for (int i = 0; i < currBcc; ++i) {
		for (auto j: BCC[i])
			cout << j << ' ';
		cout << '\n';
	}

	return 0;
}