Pagini recente » Cod sursa (job #614) | Cod sursa (job #220783) | Cod sursa (job #766431) | Cod sursa (job #112055) | Cod sursa (job #1129461)
#include<stdio.h>
#include<vector>
using namespace std;
#define nmax 100005
int n, m, i, x, y, nivac, sf, ncomp;
int niv[nmax], dfn[nmax], st[nmax], t[nmax], nrf[nmax];
vector <int> ma[nmax], comp[nmax];
vector <int> ::iterator it;
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)
{
int y;
vector <int> ::iterator it;
niv[x]=++nivac; dfn[x]=niv[x];
st[++sf]=x;
for (it=ma[x].begin();it!=ma[x].end();it++)
{
y=*it;
if ((niv[y]>0)&&(niv[y]<dfn[x])&&(y!=t[x]))
dfn[x]=niv[y];
if (niv[y]==0)
{
t[y]=x; nrf[x]++;
dfs(y);
if (dfn[y]<dfn[x])
dfn[x]=dfn[y];
if (dfn[y]>=niv[x]) /*|| ((niv[x]==1) &&(nrf[x]>1)))*/
{
ncomp++;
while (st[sf+1]!=y)
{
comp[ncomp].push_back(st[sf]);
sf--;
}
comp[ncomp].push_back(x);
}
}
}
nivac--;
}
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)
{
// ncomp++;
dfs(i);
}
afisare();
return 0;
}