Cod sursa(job #1411543)

Utilizator Marius96Marius Gavrilescu Marius96 Data 31 martie 2015 19:38:40
Problema Componente biconexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.52 kb
#include <cstdio>
#include <cstring>

#include <set>
#include <algorithm>
using namespace std;

#define N 405

static int n, u[N], w[N], z=0, r[N];
static set <int> v[N];

int df(int k, int t)
{
	int m=u[k];
	for(set<int>::iterator it = v[k].begin() ; it != v[k].end() ; it++) {
		if(!u[*it]) {
			u[*it] = u[k] + 1;
			int d = df(*it,k);
			m = min(d, m);
			if(d >= u[*it]-1)
				w[k] = -1;
		}
		else if(*it!=t)
			m = min(u[*it], m);
	}
	z -= w[k];
	return m;
}

void dfs(int k)
{
	if(!r[k])
		printf("%d ",k);
	r[k] = 1;

	for(set<int>::iterator it = v[k].begin() ; it != v[k].end() ; it++)
		if(r[*it]){
			v[*it].erase(k);
			v[k].erase(it);
		}

	if(w[k] == -1)
		return;

	for(set<int>::iterator it = v[k].begin() ; it != v[k].end() ; it++) {
		v[*it].erase(k);
		if(w[*it] == 1)
			continue;
		if(w[*it] == 0)
			w[*it]=1;
		dfs(*it);
	}

	v[k].clear(); // nu ca ar mai conta
}

int main()
{
	freopen("biconex.in","r",stdin);
#ifdef INFOARENA
	freopen("biconex.out","w",stdout);
#endif
	int m;
	scanf("%d%d",&n,&m);
	while(m--) {
		int a, b;
		scanf("%d%d",&a,&b);
		v[a].insert(b);
		v[b].insert(a);
	}

	u[1]=1;
	df(1,0);
	printf("%d\n",z+1);
	for(int i=1 ; i <= n ; i++)
		if(w[i] == -1) {
			for(set<int>::iterator it = v[i].begin() ; it != v[i].end() ; it++) {
				if(v[i].count(*it) && w[*it] < 1) { // undefined behaviour!
					if(!w[*it])
						w[*it] = 1;
					v[i].erase(it);
					v[*it].erase(i);
					r[i] = 1;
					printf("%d ", i);
					dfs(*it);
					puts("");
					memset(r, 0, sizeof r);
				}
			}
			w[i] = 1;
		}
	return 0;
}