Cod sursa(job #1781546)

Utilizator retrogradLucian Bicsi retrograd Data 16 octombrie 2016 22:56:44
Problema Componente biconexe Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
#include <bits/stdc++.h>

using namespace std;

const int kMaxN = 500005;

int Low[kMaxN], Time[kMaxN], Depth[kMaxN];
vector<int> Stack;
vector<int> G[kMaxN];

vector<vector<int>> BiComps;


void DFS(int node) {
	static int timer;

	Stack.push_back(node);
	Low[node] = Time[node] = ++timer;

	for(auto vec : G[node]) {
		if(!Time[vec]) {
			Depth[vec] = Depth[node] + 1;
			DFS(vec);
			Low[node] = min(Low[node], Low[vec]);

			if(Low[vec] >= Time[node]) {
				BiComps.push_back(vector<int>());
				auto &To = BiComps.back();
				while(true) {
					To.push_back(Stack.back());
					Stack.pop_back();
					if(To.back() == vec)
						break;
				}
				To.push_back(node);
			}
		} else if(Depth[vec] < Depth[node] - 1) {
			Low[node] = min(Low[node], Time[vec]);
		}
	}

}

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

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

	while(m--) {
		int a, b;
		cin >> a >> b;
		G[a].push_back(b);
		G[b].push_back(a);
	}

	DFS(1);

	cout << BiComps.size() << endl;
	for(auto x : BiComps) {
		for(auto y : x)
			cout << y << " ";
		cout << '\n';
	}

	return 0;
}