Pagini recente » Cod sursa (job #2344585) | Cod sursa (job #870228) | Cod sursa (job #1012962) | Cod sursa (job #2973130) | Cod sursa (job #1921810)
#include<cstdio>
#include<vector>
#include<bitset>
#include<utility>
#include<stack>
#define N 100000
using namespace std;
vector<int> vecin[N+1];
bitset<N+1> viz;
int niv[N+1];
vector<int> comp[N+1];
vector<int> ans[N+1];
int k;
stack<pair<int,int> > stk;
int stra[N+1];
void dfs(int nod,int nivel=1){
viz.set(nod);
niv[nod]=nivel;
stra[nod]=nivel-1;
for(int i=0;i<vecin[nod].size();i++){
int now=vecin[nod][i];
if (viz[now]==true) stra[nod]=min(stra[nod],niv[now]);
else {
stk.push(make_pair(nod,now));
dfs(now,nivel+1);
stra[nod]=min(stra[nod],stra[now]);
if (stra[now]>=nivel){
k++;
int x=0,y;
while(!stk.empty() &&x!=nod){
x=stk.top().first;
y=stk.top().second;
if (comp[x].empty() ||comp[x][comp[x].size()-1]!=k) comp[x].push_back(k);
if (comp[y].empty() ||comp[y][comp[y].size()-1]!=k) comp[y].push_back(k);
stk.pop();
}
}
}
}
}
int main(){
freopen ("biconex.in","r",stdin);
freopen ("biconex.out","w",stdout);
int n,m,i;
scanf ("%d%d",&n,&m);
for(i=1;i<=m;i++){
int x,y;
scanf ("%d%d",&x,&y);
vecin[x].push_back(y);
vecin[y].push_back(x);
}
dfs(1);
printf ("%d\n",k);
for(i=1;i<=n;i++)
for(int j=0;j<comp[i].size();j++)
ans[comp[i][j]].push_back(i);
for(i=1;i<=k;i++){
for(int j=0;j<ans[i].size();j++)
printf ("%d ",ans[i][j]);
printf ("\n");
}
return 0;
}