Pagini recente » Cod sursa (job #2219899) | Cod sursa (job #954672) | Cod sursa (job #2299450) | Cod sursa (job #1786810) | Cod sursa (job #953149)
Cod sursa(job #953149)
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
int N,M,x,y,v[100100],w[100100],low[100100],depth[100100],comp=0;
struct muchie
{
int nod1;
int nod2;
};
vector <muchie> m;
vector <vector <int> > c;
vector <int> a[100100];
void dfs(int k, int p, int dep)
{
v[k]=1;
depth[k]=dep;
low[k]=dep;
int d=a[k].size();
for(int i=0;i<d;++i)
{
if(v[a[k][i]]==0)
{
struct muchie z;
z.nod1=k;
z.nod2=a[k][i];
m.push_back(z);
dfs(a[k][i],k,dep+1);
low[k]=min(low[k],low[a[k][i]]);
if(low[a[k][i]]>=depth[k])
{
++comp;
vector<int> com;
int t,u,s=m.size();
do
{
t=m[s-1].nod1;
u=m[s-1].nod2;
if(w[t]!=comp)
{
w[t]=comp;
com.push_back(t);
}
if(w[u]!=comp)
{
w[u]=comp;
com.push_back(u);
}
m.pop_back();
--s;
}
while(t!=k || u!=a[k][i]);
c.push_back(com);
}
}
else if(a[k][i]!=p)
low[k]=min(low[k],depth[a[k][i]]);
}
return;
}
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);
}
for(int i=1;i<=N;++i)
if(v[i]==0)
dfs(i,0,0);
int e=c.size();
printf("%d\n",comp);
for(int i=0;i<e;++i)
{
int f=c[i].size();
for(int j=0;j<f;++j)
printf("%d ",c[i][j]);
printf("\n");
}
return 0;
}