Cod sursa(job #580124)

Utilizator aloneForever Alone alone Data 12 aprilie 2011 19:29:14
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.55 kb
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

#define NMAX 100050

struct muchie {
	int x, y;
} S[NMAX];

int niv[NMAX], low[NMAX], N, idx, nr, n, m;
vector <int> G[NMAX], C[NMAX];

void dfs (int, int), componenta (int, int), biconex (), citire (), afisare ();

int main () {
	
	citire ();
	
	biconex ();
	
	afisare ();
	
	return 0;
}

void componenta (int nod, int fiu) {
	
	int x, y;
	
	nr++;
	do {
		x = S[N].x, y = S[N].y, N--;
		C[nr].push_back (y);
	} while (x != nod || y != fiu);
	
	C[nr].push_back (x);
}

void dfs (int nod, int tata) {
	
	int fiu;
	vector <int>::iterator it;
	
	idx++;
	niv[nod] = low[nod] = idx;
	
	for (it = G[nod].begin (); it != G[nod].end (); it++) {
		fiu = *it;
		
		if (fiu == tata) continue;
		
		if (!niv[fiu]) {
			
			N++, S[N].x = nod, S[N].y = fiu;
			dfs (fiu, nod);
			
			if (low[fiu] >= niv[nod]) componenta (nod, fiu);
			
			low[nod] = min (low[nod], low[fiu]);
		}
		else
			low[nod] = min (low[nod], niv[fiu]);
	}
}

void biconex () {
	
	for (int i = 1; i <= n; i++)
		if (!niv[i]) dfs (i, 0);
}

void citire () {
	
	ifstream f ("biconex.in");
	
	int i, x, y;
	
	f >> n >> m;
	
	for (i = 1; i <= m; i++) {
		f >> x >> y;
		G[x].push_back (y);
		G[y].push_back (x);
	}
	
	f.close ();
}

void afisare () {
	
	ofstream g ("biconex.out");
	
	g << nr << "\n";
	
	for (int i = 1; i <= nr; i++) {
		for (vector <int>::iterator it = C[i].begin (); it != C[i].end (); it++)
			g << *it << " ";
		g << "\n";
	}
}