Pagini recente » Cod sursa (job #2265758) | Cod sursa (job #2518609) | Cod sursa (job #1354651) | Cod sursa (job #768780) | Cod sursa (job #471704)
Cod sursa(job #471704)
#include <stdio.h>
#include <vector>
#include <stack>
#include <set>
#define Nmax 100005
#define Mmax 200005
#define pb push_back
#define mp make_pair
#define x first
#define y second
using namespace std;
vector< int > v[Nmax];
stack< pair<int,int> > S;
vector< set< int > > Cb;
int dfn[Nmax],low[Nmax];
int n,m,nr=0;
inline int Minim(int x,int y){ return x<y ? x:y; }
void comp_bicon(int u,int tu){
set< int > aux;
pair< int, int > p;
do{
p=S.top(); S.pop();
aux.insert(p.x); aux.insert(p.y);
} while( p.x != tu && p.y!=u);
Cb.pb(aux);
}
void Df(int u, int tu){
vector< int >:: iterator it;
dfn[u]=low[u]=++nr;
for(it=v[u].begin(); it!=v[u].end(); ++it){
if( *it==tu ) continue;
if( dfn[*it]==-1 ){
S.push(mp(u,*it));
Df(*it,u);
low[u]=Minim(low[u],low[*it]);
if( low[*it] >= dfn[u] )
comp_bicon(*it,u);
}
else
low[u]=Minim(low[u],dfn[*it]);
}
}
int main(){
int i,x,y;
set< int >:: iterator sit;
freopen("biconex.in","r",stdin);
freopen("biconex.out","w",stdout);
scanf("%d%d",&n,&m);
for(i=1;i<=m;++i){
scanf("%d%d",&x,&y);
v[x].pb(y);
v[y].pb(x);
}
for(i=1;i<=n;++i) dfn[i]=low[i]=-1;
Df(1,0);
printf("%d\n",Cb.size());
for(size_t it=0; it<Cb.size(); ++it){
for( sit=Cb[it].begin(); sit!=Cb[it].end(); ++sit)
printf("%d ",*sit);
printf("\n");
}
fclose(stdin); fclose(stdout);
return 0;
}