Pagini recente » Cod sursa (job #204795) | Rating Radutoiu Miruna (MiryBlue) | Preoni 2006 | Monitorul de evaluare | Cod sursa (job #1411543)
#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;
}