Cod sursa(job #954819)

Utilizator gabrieligabrieli gabrieli Data 30 mai 2013 07:28:52
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 kb
#include <algorithm>
#include <cstdlib>
#include <fstream>
#include <iostream>
#include <stack>
#include <utility>
#include <vector>
using namespace std;

const size_t MAXN = 100010;
int idx = 1;

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

void DFS (int v, int parent, 
		vector <int> &dfsIdx, vector <int> &lowIdx, 
		vector <int> (&G)[MAXN], stack <pair <int, int>> &edges,
		vector <vector <int>> &BC)
{
	dfsIdx[v] = lowIdx[v] = idx++;
	for (auto &n : G[v])
		if (n == parent) continue;
		else if (dfsIdx[n] == 0)
		{
			edges.push (make_pair (v, n));
			
			DFS (n, v, dfsIdx, lowIdx, G, edges, BC);

			lowIdx[v] = min (lowIdx[v], lowIdx[n]);

			if (lowIdx[n] >= dfsIdx[v])
			{
				int x, y;
				BC.push_back (vector <int>());

				do {
					x = edges.top().first;
					y = edges.top().second;
					edges.pop();

					BC.back().push_back (y);
				} while (x != v && y != n);
				BC.back().push_back (v);
			}
		}
		else lowIdx[v] = min (lowIdx[v], lowIdx[n]);
}

int main()
{
	int N, m;
	vector <int> G[MAXN];
	vector <vector <int>> BC;
	
	for (fin >> N >> m; m; --m)
	{
		int x, y;
		fin >> x >> y;
		G[x].push_back (y);
		G[y].push_back (x);
	}

	vector <int> dfsIdx (N+1, 0), lowIdx (N+1);
	stack <pair <int, int>> edges;

	for (int v = 1; v <= N; ++v)
		if (!dfsIdx[v])
		{
			DFS (v, 0, dfsIdx, lowIdx, G, edges, BC);
		}

	fout << BC.size() << '\n';
	for (auto &bc : BC)
	{
		for (auto &v : bc)
			fout << v << ' ';
		fout << '\n';
	}

	return EXIT_SUCCESS;
}