Cod sursa(job #530296)

Utilizator ciprianfFarcasanu Alexandru Ciprian ciprianf Data 7 februarie 2011 14:26:26
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.41 kb
#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
#define NMAX 100010
#define FOR(i, v) for(vector<int>::iterator i = v.begin(); i != v.end(); ++i)
vector <int> G[NMAX], SOL[NMAX];
int viz[NMAX];
int L[NMAX], c[NMAX];
int st[NMAX][2];
int tata[NMAX];
int n, m, k;
int sol;
void dfs(int x) {
	viz[x] = 1;
	c[x] = L[x];
	FOR(i, G[x])
		if(!viz[*i]){
			L[*i] = L[x] + 1;
			tata[*i] = x;
			st[++k][0] = x;
			st[k][1] = *i;
			dfs(*i);
			if(c[*i] < c[x]) c[x] = c[*i];
			
			if(c[*i] >= L[x]){
				sol++;
				while( !( st[k][0] == x && st[k][1] == *i)){
					SOL[sol].push_back(st[k][1]);
					SOL[sol].push_back(st[k][0]);
					k--;
				}
				SOL[sol].push_back(st[k][1]);
				SOL[sol].push_back(st[k][0]);
				k--;
			}
		}
		else if(tata[x] != *i && L[*i] < L[x]){
			if(c[x] > L[*i]) c[x] = L[*i];
			st[++k][0] = x;
			st[k][1] = *i;
		}
		
}			
int main(){
	freopen("biconex.in", "r", stdin);
	freopen("biconex.out", "w", stdout);
	scanf("%d%d", &n, &m);
	for(int i =  1; i <= m; ++i){
		int x, y;
		scanf("%d%d", &x, &y);
		G[x].push_back(y);
		G[y].push_back(x);
	}
	dfs(1);
	printf("%d\n", sol);
	for(int i = 1; i <= sol; ++i) {
		sort(SOL[i].begin(), SOL[i].end());
		printf("%d", *SOL[i].begin());
		for(unsigned int j = 1; j < SOL[i].size(); ++j)
			if(SOL[i][j] != SOL[i][j-1]) printf(" %d", SOL[i][j]);
		printf("\n");
	}
	return 0;
}