Pagini recente » Cod sursa (job #1566996) | Cod sursa (job #2593089) | Cod sursa (job #1398970) | Cod sursa (job #1308630) | Cod sursa (job #604744)
Cod sursa(job #604744)
#include <stdio.h>
#include <algorithm>
#include <vector>
#define NMax 100010
using namespace std;
const char IN[]="biconex.in",OUT[]="biconex.out";
int N,M;
int lvl[NMax],low[NMax];
vector<int> ad[NMax];
vector<pair<int,int> > v;
vector<vector<int> > Sol;
void upd(int x,int y)
{
vector<int> c;
int tx,ty;
do{
tx=(v.end()-1)->first;ty=(v.end()-1)->second;
v.pop_back();
c.push_back(tx);c.push_back(ty);
}
while (tx!=x || ty!=y);
Sol.push_back(c);
}
void bfs(int x=1,int p=0,int lv=1)
{
lvl[x]=low[x]=lv;
for (vector<int>::iterator it=ad[x].begin();it!=ad[x].end();++it)
{
if (p==*it) continue;
if (!lvl[*it])
{
v.push_back(make_pair(x,*it));
bfs(*it,x,lv+1);
low[x]= min(low[x],low[*it]);
if (low[*it]>=lvl[x])
upd(x,*it);
}
else
low[x]= min(low[x],lvl[*it]);
}
}
int main()
{
int x,y;
freopen(IN,"r",stdin);
scanf("%d%d",&N,&M);
while (M--)
scanf("%d%d",&x,&y),
ad[x].push_back(y),
ad[y].push_back(x);
fclose(stdin);
bfs();
freopen(OUT,"w",stdout);
printf("%d\n",Sol.size());
for (int i=0;i<(int)Sol.size();++i)
{
sort(Sol[i].begin(),Sol[i].end());
Sol[i].erase(unique(Sol[i].begin(),Sol[i].end()),Sol[i].end());
for (typeof(Sol[i].begin()) it2=Sol[i].begin();it2<Sol[i].end();++it2)
printf("%d ",*it2);
printf("\n");
}
fclose(stdout);
return 0;
}