Cod sursa(job #961887)

Utilizator gabrieligabrieli gabrieli Data 13 iunie 2013 08:43:18
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.48 kb
#include <cstdlib>
#include <fstream>
#include <iostream>
#include <stack>
#include <utility>
#include <vector>
using namespace std;

int DFSINDEX = 1;
stack <pair <size_t, size_t>> edges;

void dfs (size_t v, size_t parent, 
		vector <size_t> &dfsReach, vector <size_t> &dfsIndex,
		vector <vector <size_t>> &G, vector <vector <size_t>> &C)
{
	dfsIndex[v] = dfsReach[v] = DFSINDEX++;

	for (auto &n : G[v])
		if (n == parent) continue;
		else if (dfsIndex[n] == 0)
		{
			edges.push (make_pair (v, n));
			dfs (n, v, dfsReach, dfsIndex, G, C);
			if (dfsReach[v] > dfsReach[n])
				dfsReach[v] = dfsReach[n];

			if (dfsReach[n] >= dfsIndex[v])
			{
				C.push_back(vector <size_t>());
				int x, y;
				do {
					x = edges.top().first;
					y = edges.top().second;
					edges.pop();

					C.back().push_back (y);
				} while (x != v && y != n);
				C.back().push_back(v);
			}
		}
		else if (dfsReach[v] > dfsReach[n])
			dfsReach[v] = dfsReach[n]; 
}

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

	size_t N, m;

	fin >> N >> m;
	vector <vector <size_t>> G(N+1), C;
	vector <size_t> dfsIndex(N+1, 0), dfsReach(N+1);

	for (; m; --m)
	{
		int x, y;
		fin >> x >> y;
		G[x].push_back(y);
		G[y].push_back(x);
	}

	for (size_t v = 1; v <= N; ++v)
		if (dfsIndex[v] == 0)
			dfs (v, 0, dfsReach, dfsIndex, G, C);

	fout << C.size() << '\n';
	for (auto &component : C)
	{
		for (auto &vertex : component)
			fout << vertex << ' ';
		fout << '\n';
	}
	fout.close();
	return EXIT_SUCCESS;
}