Cod sursa(job #1359805)

Utilizator DuxarFII-Stefan-Negrus Duxar Data 25 februarie 2015 07:49:58
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.42 kb
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>
#include <stack>

using namespace std;

int N, M, ans = -1;
vector <vector <int> > components, graph;
vector <int> height, down;
stack <pair <int, int> > edges;

void DFS(int iam, int from);

int main() {
#ifdef INFOARENA
	freopen("biconex.in", "r", stdin);
	freopen("biconex.out", "w", stdout);
#else
#endif
	
	int x, y, i;
	scanf("%d %d", &N, &M);
	
	graph.resize(N + 1);
	height.resize(N + 1, -1);
	down.resize(N + 1);
	
	for (i = 1; i <= M; ++i) {
		scanf("%d %d", &x, &y);
		graph[x].push_back(y);
		graph[y].push_back(x);
	}
	
	for (i = 1; i <= N; ++i) {
		if (height[i] == -1) {
			DFS(i, 1);
		}
	}
	
	printf("%d\n", ans + 1);
	for (auto cmp: components) {
		for (auto x: cmp) {
			printf("%d ", x);
		}
		printf("\n");
	}
	
	return 0;
}

void DFS(int iam, int from) {
	height[iam] = height[from] + 1;
	down[iam] = height[iam];
	for (auto to: graph[iam]) {
		if (height[to] == -1) {
			edges.push({iam, to});
			DFS(to, iam);
			down[iam] = min(down[iam], down[to]);
			if (down[to] >= height[iam]) {
				components.push_back(vector <int> ());
				++ans;
				while (!(edges.top().first == iam && edges.top().second == to)) {
					components[ans].push_back(edges.top().second);
					edges.pop();
				}
				edges.pop();
				components[ans].push_back(to);
				components[ans].push_back(iam);
			}
		}
		else if (to != from) {
			down[iam] = min(down[iam], height[to]);
		}
	}
}