Cod sursa(job #631016)

Utilizator mihaibogdan10Mihai Bogdan mihaibogdan10 Data 6 noiembrie 2011 20:23:39
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.73 kb
#include<cstdio>
#include<vector>
#define min(a,b) a < b ? a : b
using namespace std;
FILE *in = fopen("biconex.in", "r"), *out = fopen("biconex.out", "w");

int n, m, index;
vector <int> graf[100001], viz(100001, 0), bcStack, lowlink (100001, 0), tata(100001, 0), vindex(100001, 0);
vector <vector <int> > sol;

void BC(int nod){
	bcStack.push_back(nod);
	lowlink[nod] = vindex[nod] = ++index;
	viz[nod] = 1;
	int i, adiacent;
	vector <int> newbc;
	
	for (i = 0; i < (int)graf[nod].size(); i++){
		adiacent = graf[nod][i];
		
		if (!viz[adiacent]) {
			tata[adiacent] = nod;
			BC(adiacent);
			// la intoarcerea din recursie, lowlink[tata] = min lowlink[fii]
			lowlink[nod] = min (lowlink[nod], lowlink[adiacent]);
		}
		// am intalnit o muchie de intoarcere
		else if (tata[nod] != adiacent) 
			lowlink[nod] = min (lowlink[nod], lowlink[adiacent]);		
	}
	
	if (lowlink[nod] == vindex[nod]){
		newbc.clear();
		do	{
			adiacent = bcStack.back(), bcStack.pop_back();
			newbc.push_back(adiacent);
		}
		while (nod != adiacent);		
		if (newbc.size() > 1)sol.push_back(newbc);
		//daca este cazul, adauga comp biconexa formata din nodul de articulatie si tatal lui
		if (tata[nod]){
			newbc.clear();
			newbc.push_back(nod), newbc.push_back(tata[nod]);
			sol.push_back(newbc);
		}
	}
}

int main(){
	int i, j, x, y;
	fscanf(in, "%d %d", &n, &m);
	for (i = 0; i <= m; i++){
		fscanf(in, "%d %d", &x, &y);
		graf[x].push_back(y);
		graf[y].push_back(x);
	}
	
	for (i = 1; i <= n ;i++)
		if (!viz[i])
			BC(i);
	
	fprintf(out, "%d\n", sol.size());
	for (i = 0; i < (int)sol.size(); i++){
		for (j = 0; j < (int)sol[i].size(); j++)
			fprintf(out, "%d ", sol[i][j]);
		fprintf(out, "\n");
	}
	
	return 0;
}