Cod sursa(job #1339512)

Utilizator iordache.bogdanIordache Ioan-Bogdan iordache.bogdan Data 10 februarie 2015 22:43:07
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <stack>

#define DIM 100005
#define vint vector<int>::iterator
#define infile "biconex.in"
#define outfile "biconex.out"

using namespace std;

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

int n, m;

bool ok[DIM];

int Niv[DIM], Low[DIM];

int nrBiConexe;

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

stack<int> Stack;

void DFS(int node, int lvl) {

	ok[node] = 1;

	Niv[node] = lvl;
	Low[node] = lvl;

	Stack.push(node);

	for (vint it = L[node].begin(); it != L[node].end(); ++it) {

		if (ok[*it]) {

			Low[node] = std::min(Low[node], Niv[*it]);
			continue;

		}

		DFS(*it, lvl + 1);

		Low[node] = std::min(Low[node], Low[*it]);

		if (Niv[node] <= Low[*it]) {

			++nrBiConexe;

			int x;

			do {

				x = Stack.top();

				Stack.pop();

				biConexe[nrBiConexe].push_back(x);

			} while (x != *it);

			biConexe[nrBiConexe].push_back(node);

		}

	}

}

int main() {

	f >> n >> m;

	for (int i = 1; i <= m; ++i) {

		int x, y;

		f >> x >> y;

		L[x].push_back(y);
		L[y].push_back(x);

	}

	memset(ok, false, sizeof(ok));

	for (int i = 1; i <= n; ++i)
		if (!ok[i])
			DFS(i, 1);

	g << nrBiConexe << '\n';

	for (int i = 1; i <= nrBiConexe; ++i) {

		for (vint it = biConexe[i].begin(); it != biConexe[i].end(); ++it)
			g << *it << ' ';

		g << '\n';

	}

	return 0;
}

//Trust me, I'm the Doctor!