Cod sursa(job #1680470)

Utilizator Cristian1997Vintur Cristian Cristian1997 Data 8 aprilie 2016 19:59:40
Problema Componente biconexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.47 kb
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
#define pii pair<int,int>
#define Nmax 100001

vector< int > G[Nmax];
vector< vector< int > > comp;
//vector< bool > critic(Nmax);
stack< pii > stk;
int low[Nmax], d[Nmax];
int n, time = 0;

void DFS(int, int);
void cache(int, int);

int main()
{
	int i, m, a, b;
	ifstream fin("biconex.in");
	ofstream fout("biconex.out");

	fin >> n >> m;
	for (; m; --m)
	{
		fin >> a >> b;
		G[a].push_back(b);
		G[b].push_back(a);
	}

	for (i = 1; i <= n; ++i)
		if (low[i] == 0) DFS(i, 0);

	fout << comp.size() << '\n';
	for (auto &vec : comp)
	{
		for (auto &node : vec)
			fout << node << ' ';
		fout << '\n';
	}

	return 0;
}

void DFS(int vf, int f)
{
	++time;
	low[vf] = d[vf] = time;

	for (auto &it : G[vf])
	{
		if (it == f) continue;

		if (low[it] == 0)
		{
			stk.push(make_pair(it, vf));

			DFS(it, vf);

			if (low[vf] > low[it]) low[vf] = low[it];
			if (low[it] >= d[vf]) cache(it, vf);
		}
		else if (d[it] < low[vf]) low[vf] = d[it];
	}

	++time;
}


void cache(int vf, int f)
{
	int tx, ty;

	comp.push_back(vector<int>());

	do
	{
		tx = stk.top().first;
		ty = stk.top().second;

		comp.back().push_back(tx);
		comp.back().push_back(ty);
		stk.pop();
	} while (ty != f);

	sort(comp.back().begin(), comp.back().end());
	comp.back().erase(unique(comp.back().begin(), comp.back().end()), comp.back().end());
}