Cod sursa(job #1228589)

Utilizator iordache.bogdanIordache Ioan-Bogdan iordache.bogdan Data 14 septembrie 2014 17:32:24
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include <fstream>
#include <vector>
#include <stack>
#define DIM 100005
#define vint vector<int>::iterator
#define minim(a, b) (a < b ? a : b)
#define infile "biconex.in"
#define outfile "biconex.out"

using namespace std;

ifstream f(infile);
ofstream g(outfile);

vector<int> L[DIM], Sol[DIM];

stack<int> s;

int n, m, a, b, sol;

int Niv[DIM], Low[DIM];

void DFS(int nod, int niv) {
	Niv[nod] = niv;
	Low[nod] = niv;
	s.push(nod);
	for (vint it = L[nod].begin(); it != L[nod].end(); ++it)
	if (Niv[*it] == 0) {
		DFS(*it, niv + 1);
		Low[nod] = minim(Low[nod], Low[*it]);
		if (Niv[nod] <= Low[*it]) {
			++sol;
			while (s.top() != *it) {
				Sol[sol].push_back(s.top());
				s.pop();
			}
			Sol[sol].push_back(*it);
			s.pop();
			Sol[sol].push_back(nod);
		}
	}
	else
		Low[nod] = minim(Low[nod], Niv[*it]);
}

int main() {
	f >> n >> m;
	for (int i = 1; i <= m; ++i) {
		f >> a >> b;
		L[a].push_back(b);
		L[b].push_back(a);
	}
	for (int i = 1; i <= n; ++i)
	if (Niv[i] == 0)
		DFS(i, 1);
	g << sol << "\n";
	for (int i = 1; i <= sol; ++i) {
		for (vint it = Sol[i].begin(); it != Sol[i].end(); ++it)
			g << *it << " ";
		g << "\n";
	}
	return 0;
}