Cod sursa(job #1363367)

Utilizator catalincraciunCraciun Catalin catalincraciun Data 26 februarie 2015 22:07:47
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.39 kb
// biconex
#include <iostream>
#include <fstream>
#include <algorithm>
#include <stack>
#include <vector>

#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 best[NMax], lvl[NMax];
stack< pair<int, int> > M;
vector< vector<int> > sol;

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;
	while (1) {
		bool ok = (M.top().first != x || M.top().second != y);
		C.pb(M.top().first);
		C.pb(M.top().second);
		M.pop();
		if (!ok) break;
		if (M.empty()) 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] == 0) {
			M.push(mp(node,vecin));
			dfs(vecin, node);
			if (best[vecin] >= lvl[node])
				addComp(node, vecin);
			best[node] = min(best[node], best[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();
	dfs(1,0);
	output();

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