Pagini recente » Cod sursa (job #2674902) | Cod sursa (job #2508466) | Cod sursa (job #2224480) | Cod sursa (job #2407271) | Cod sursa (job #1164014)
#include<stdio.h>
#include<vector>
using namespace std;
#define nmax 100005
int n, m, i, x, y, sf, ncomp;
vector <int> ma[nmax], comp[nmax];
vector <int> ::iterator it;
int st[nmax], niv[nmax], t[nmax], dfn[nmax];
void citire()
{
scanf("%ld %ld",&n,&m);
for (i=1;i<=m;i++)
{
scanf("%ld %ld",&x,&y);
ma[x].push_back(y); ma[y].push_back(x);
}
}
void dfs(int x)
{
vector <int> ::iterator it;
int y;
niv[x]=niv[t[x]]+1; st[++sf]=x;
dfn[x]=niv[x];
for (it=ma[x].begin();it!=ma[x].end();it++)
{
y=*it;
if ((niv[y]>0)&&(y!=t[x])&&(niv[y]<dfn[x]))
dfn[x]=niv[y];
if (niv[y]==0)
{
t[y]=x;
dfs(y);
if (dfn[y]<dfn[x])
dfn[x]=dfn[y];
if (dfn[y]>=niv[x])
{
ncomp++;
while(st[sf+1]!=y)
{
comp[ncomp].push_back(st[sf]);
sf--;
}
comp[ncomp].push_back(x);
}
}
}
}
void afisare()
{
printf("%ld\n",ncomp);
for (i=1;i<=ncomp;i++)
{
for (it=comp[i].begin();it!=comp[i].end();it++)
printf("%ld ",*it);
printf("\n");
}
}
int main()
{
freopen("biconex.in","r",stdin);
freopen("biconex.out","w",stdout);
citire();
for (i=1;i<=n;i++)
if (niv[i]==0)
dfs(i);
afisare();
return 0;
}