Pagini recente » Cod sursa (job #524370) | Cod sursa (job #1115588) | Cod sursa (job #1700454) | Cod sursa (job #1538427) | Cod sursa (job #1509348)
#include<stdio.h>
#include<vector>
#include<algorithm>
#define pb push_back
#define mp make_pair
#define fs first
#define sc second
using namespace std;
int M,x,y;
int N,w[100100],low[100100],depth[100100],comp;
bool viz[100100];
vector<pair<int,int> > m;
vector <vector <int> > c;
vector <int> a[100100],com;
void dfs(int x, int p, int dep) {
viz[x] = 1; depth[x]=dep; low[x]=dep;
for(auto y: a[x]) {
if(!viz[y]) {
m.pb(mp(x,y)); dfs(y,x,dep+1);
low[x] = min(low[x],low[y]);
if(low[y] >= depth[x]) {
++comp; com.clear();
while(true) {
int t = m.back().fs, u = m.back().sc;
if(w[t] != comp) {
w[t] = comp; com.pb(t);
}
if(w[u] != comp) {
w[u] = comp; com.pb(u);
}
m.pop_back();
if(t==x && u==y) break;
}
c.pb(com);
}
} else if(y!=p) {
low[x]=min(low[x],depth[y]);
}
}
}
void biconex() {
for(int i=1;i<=N;++i) {
if(!viz[i]) {
dfs(i,0,0);
}
}
}
int main()
{
freopen("biconex.in","r",stdin);
freopen("biconex.out","w",stdout);
scanf("%d%d",&N,&M);
for(int i=1;i<=M;++i) {
scanf("%d%d",&x,&y);
a[x].push_back(y);
a[y].push_back(x);
}
biconex();
printf("%d\n",c.size());
for(auto x: c) {
for(auto y: x) {
printf("%d ",y);
}
printf("\n");
}
return 0;
}