Pagini recente » Cod sursa (job #3000094) | Cod sursa (job #23199) | Cod sursa (job #1378501) | Cod sursa (job #2621430) | Cod sursa (job #521608)
Cod sursa(job #521608)
#include <cstdio>
#include <stack>
#include <bitset>
#include <algorithm>
#include <vector>
using namespace std;
#define N 100010
#define fs first
#define sc second
#define mp make_pair
#define pii pair< int,int >
#define pb push_back
template< class T >
inline T minim(const T &x,const T &y) {
return ( (x<y) ? x : y );
}
int n;
vector< int > a[N];
int ind[N],indlow[N],indice;
stack< int > st;
vector< vector< int > > bicon;
int nrez;
bitset< N > viz;
inline void citire() {
int m,x,y;
scanf("%d%d",&n,&m);
for(int i=0; i<m; ++i) {
scanf("%d%d",&x,&y);
a[x].pb(y);
a[y].pb(x);
}
}
void dfs(int nod,int tata) {
++indice;
ind[nod] = indlow[nod] = indice;
int nod1;
for(size_t i=0,lim=a[nod].size(); i<lim; ++i) {
nod1 = a[nod][i];
if(nod1==tata)
continue;
if(ind[nod1]==0) {
st.push(nod);
dfs(nod1,nod);
if(indlow[nod1]>=ind[nod]) {
bicon.resize(nrez+1);
do {
nod1 = st.top();
st.pop();
bicon[nrez].pb(nod1);
}while(nod1!=nod);
++nrez;
} else
indlow[nod] = indlow[nod1];
} else
indlow[nod] = minim(indlow[nod1],indlow[nod]);
}
st.push(nod);
}
inline void scrie() {
printf("%d\n",nrez);
for(int i=0; i<nrez; ++i) {
viz.reset();
for(size_t j=0,lim=bicon[i].size(); j<lim; ++j) {
if(viz[bicon[i][j]]==1)
continue;
viz[bicon[i][j]] = 1;
printf("%d ",bicon[i][j]);
}
printf("\n");
}
}
int main() {
freopen("biconex.in","r",stdin);
freopen("biconex.out","w",stdout);
citire();
for(int i=1; i<=n; ++i) {
if(ind[i]!=0)
continue;
dfs(i,0);
}
scrie();
return 0;
}