Pagini recente » Cod sursa (job #2987511) | Cod sursa (job #2242796) | Cod sursa (job #164997) | Cod sursa (job #1092825) | Cod sursa (job #994777)
Cod sursa(job #994777)
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
struct muchie {
int a,b;
muchie() {
a=b=0;
}
muchie(int x,int y) {
a=x;
b=y;
}
};
const int MAX_N=100100;
const int MAX_M=100100;
vector<int> A[MAX_N];
int h[MAX_N];
int hmin[MAX_N];
muchie st[MAX_M];
int size;
vector< vector<int> > ans;
void make_bc(int x,int y) {
vector<int> sol;
int a=st[size].a,b=st[size].b;
size--;
sol.push_back(a);
sol.push_back(b);
while(size&&(a!=x||b!=y) ) {
a=st[size].a,b=st[size].b;
size--;
sol.push_back(a);
sol.push_back(b);
}
sort(sol.begin(),sol.end());
vector<int>:: iterator it=unique(sol.begin(),sol.end());
sol.erase(it,sol.end());
ans.push_back(sol);
}
int dfs(int nod,int str,int ad) {
h[nod]=ad;
hmin[nod]=ad;
for(vector<int>::iterator it=A[nod].begin();it!=A[nod].end();it++) {
if(*it!=str) {
if(!h[*it]) {
st[++size]=muchie(nod,*it);
dfs(*it,nod,ad+1);
hmin[nod]=min(hmin[nod],hmin[*it]);
if(hmin[*it]>=ad)
make_bc(nod,*it);
}
else {
hmin[nod]=min(hmin[nod],h[*it]);
}
}
}
}
int main() {
freopen("biconex.in","r",stdin);
freopen("biconex.out","w",stdout);
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++) {
int a,b;
scanf("%d%d",&a,&b);
A[a].push_back(b);
A[b].push_back(a);
}
dfs(1,0,1);
printf("%d\n",ans.size());
for(int i=0;i<ans.size();i++,printf("\n")) {
for(vector<int>::iterator it=ans[i].begin();it!=ans[i].end();it++) {
printf("%d ",*it);
}
}
return 0;
}