Cod sursa(job #1366352)

Utilizator ooptNemes Alin oopt Data 28 februarie 2015 23:14:02
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.47 kb
// biconex
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
#include <cstring>

#define pb push_back
#define mp make_pair
#define NMax 100005

using namespace std;

ifstream f("biconex.in");
ofstream g("biconex.out");

int n,m;
vector<int> V[NMax];
int lvl[NMax], best[NMax];
vector< vector<int> > sol;
stack< pair<int, int> > muc;

void read() {
	f>>n>>m;
	for (int i=1;i<=m;i++) {
		int a,b;
		f>>a>>b;
		V[a].pb(b);
		V[b].pb(a);
	}
}

void addComp(int x, int y) {
	vector<int> c; c.resize(0);

	while (1) {
		int nod1 = muc.top().first;
		int nod2 = muc.top().second;
		muc.pop();
		c.pb(nod1); c.pb(nod2);

		if (muc.empty()) break;
		if (nod1 == x && nod2 == y) break;
	}

	sort(c.begin(), c.end());
	c.erase(unique(c.begin(), c.end()), c.end());
	sol.pb(c);
}

void dfs(int node, int father) {
	best[node] = lvl[node] = lvl[father]+1;
	for (unsigned i=0;i<V[node].size();i++) {
		int vecin = V[node][i];
		if (vecin == father) continue;

		if (lvl[vecin] == -1) {
			muc.push(mp(node, vecin));
			dfs(vecin, node);
			best[node] = min(best[node], best[vecin]);
			if (best[vecin] >= lvl[node])
				addComp(node, vecin);
		} else
			best[node] = min(best[node], lvl[vecin]);
	}
}

void output() {
	g<<sol.size()<<'\n';
	for (unsigned i=0;i<sol.size();i++) {
		for (unsigned j=0;j<sol[i].size();j++)
			g<<sol[i][j]<<' ';
		g<<'\n';
	}
}

int main() {

	read();
	memset(lvl, -1, sizeof(lvl));
	dfs(1,0);
	output();

	f.close(); g.close();
	return 0;
}