Cod sursa(job #1273772)

Utilizator mircea.dobreanuMircea Dobreanu mircea.dobreanu Data 22 noiembrie 2014 22:23:32
Problema Componente biconexe Scor 58
Compilator cpp Status done
Runda Arhiva educationala Marime 1.47 kb
#include <algorithm>
#include <fstream>
#include <stack>
#include <utility>
#include <vector>
using namespace std;

vector<vector<int>> adj, comp;
vector<int> dfn, low;
vector<bool> vis;
stack<pair<int,int>> s;

void read()
{
	ifstream fin("biconex.in");
	int n, m;
	fin >> n >> m;

	adj.resize(n + 1);
	dfn.resize(n + 1);
	low.resize(n + 1);
	vis.resize(n + 1);
	fill(low.begin(), low.end(), (1 << 30));


	for (int i = 0; i < m; ++i)
	{
		int x, y;
		fin >> x >> y;
		adj[x].push_back(y);
		adj[y].push_back(x);
	}
	fin.close();
}
void write()
{
	ofstream fout("biconex.out");
	fout << comp.size() << '\n';
	for (auto bc : comp)
	{
		for (auto i : bc)
			fout << i << ' ';
		fout << '\n';
	}
	fout.close();
}
//Component that starts with u
void add_component(pair<int, int> p)
{
	vector<int> bc;
	while (s.top() != p)
	{
		bc.push_back(s.top().second); bc.push_back(s.top().first);
		s.pop();
	}
	//Add the p pair
	bc.push_back(s.top().second); bc.push_back(s.top().first);
	s.pop();

	//Remove repeating nodes
	bc.erase(unique(bc.begin(), bc.end()), bc.end());
	sort(bc.begin(), bc.end());
	comp.push_back(bc);
}
void dfs(int u, int parent, int lvl)
{
	vis[u] = true;
	dfn[u] = lvl;
	low[u] = lvl;
	for (int v : adj[u])
	{
		if (v == parent)
			continue;
		if (vis[v] == false)
		{
			s.push(make_pair(u, v));
			dfs(v, u, 1 + dfn[u]);
			if (low[v] >= dfn[u])
				add_component(make_pair(u, v));
		}
		low[u] = min(low[u], low[v]);
	}
}

int main()
{
	read();	
	dfs(1, -1, 0);
	write();
	return 0;
}