Cod sursa(job #1394680)

Utilizator taigi100Cazacu Robert taigi100 Data 20 martie 2015 16:09:32
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
#include <fstream>
#include <vector>
#include <stack>
#include <cstring>
using namespace std;

const int kMaxN = 100005;

ifstream fin("biconex.in");
ofstream fout("biconex.out");

int N, M;
vector<int> G[kMaxN];

bool use[kMaxN];
int level[kMaxN], low[kMaxN];
stack<int> st;
vector<vector<int>> sol;

void AddComponent(int node, int son) {
	vector<int> crt;
	while (st.top() != son) {
		crt.push_back(st.top());
		st.pop();
	}
	st.pop();
	crt.push_back(son);
	crt.push_back(node);
	sol.push_back(crt);
}

void DFS(int node, int padre) {
	use[node] = true;
	for (int i : G[node]) {
		if (i == padre)
			continue;
		if (use[i]) {
			low[node] = min(low[node], level[i]);
		} else {
			st.push(i);
			level[i] = level[node] + 1;
			DFS(i, node);
			low[node] = min(low[node], low[i]);
			if (!padre || low[i] >= level[node])
				AddComponent(node, i);
		}
	}
}

int main() {
	fin >> N >> M;
	while (M--) {
		int x, y;
		fin >> x >> y;
		G[x].push_back(y);
		G[y].push_back(x);
	}
	memset(low, 0x3f, sizeof low);
	for (int i = 1; i <= N; ++i)
		if (!use[i])
			DFS(i, 0);
	fout << sol.size() << "\n";
	for (const auto &crt : sol) {
		for (int i : crt)
			fout << i << " ";
		fout << "\n";
	}
	return 0;
}