Cod sursa(job #1363153)

Utilizator ooptNemes Alin oopt Data 26 februarie 2015 19:16:21
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.53 kb
// biconex
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <cstring>
#include <algorithm>

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

using namespace std;

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

int n, m;
vector<int> V[NMax];
stack< pair<int, int> > M; // Muchii
int lvl[NMax];
int best[NMax];
vector< vector<int> > comps;

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) {
	cout<<x<<' '<<y<<endl;
	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());
	auto it = unique(C.begin(), C.end());
	C.erase(it, C.end());
	comps.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) {
			M.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<<comps.size()<<'\n';
	for (unsigned i=0;i<comps.size();i++) {
		for (unsigned j=0;j<comps[i].size();j++)
			g<<comps[i][j]<<' ';
		g<<'\n';
	}
}

int main() {

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

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