Pagini recente » Cod sursa (job #179154) | Cod sursa (job #913648) | Cod sursa (job #1568705) | Cod sursa (job #2456499) | Cod sursa (job #686336)
Cod sursa(job #686336)
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
#define nrmaxv 100010
int n,num,nr,m,VfS,s[nrmaxv], dfn[nrmaxv], low[nrmaxv];
vector<int> a[nrmaxv],q[nrmaxv];
void citire();
void biconex(int,int);
void initializare();
void afisare();
int main()
{
freopen("biconex.out","w",stdout);
citire();
initializare();
for(int i=1;i<=n;i++)
if(!(dfn[i]+1))
biconex(i,-1);
printf("%d\n",nr);
afisare();
return 0;
}
void citire()
{
freopen("biconex.in","r",stdin);
scanf("%d%d",&n,&m);
int x,y,i;
for(i=1;i<=m;i++)
{
scanf("%d%d", &x,&y);
a[x].push_back(y);
a[y].push_back(x);
}
}
void initializare()
{
int i;
for(i=1;i<=n;i++)
dfn[i]=-1;
VfS=0;
}
int min(int x, int y)
{
if(x<y)return x;
return y;
}
void biconex(int u, int tu)
{
int x;
vector<int>::iterator it;
dfn[u]=low[u]=++num;
for(it=a[u].begin();it!=a[u].end();it++)
{
x=*it;
if(x!=tu)
{
if(dfn[x]==-1)
{
s[++VfS]=x;
s[++VfS]=u;
biconex(x,u);
low[u]=min(low[u],low[x]);
if(low[x]>=dfn[u])
{
nr++;
int i;
i=VfS;
while(s[i-1]!=x&&s[i]!=u)
i-=2;
i-=1;
sort(s+i,s+VfS+1);
q[nr].push_back(s[i]);
for(int j=i+1;j<=VfS;j++)
if(s[j]!=s[j-1])
q[nr].push_back(s[j]);
VfS=i-1;
}
}
else
low[u]=min(low[u],low[x]);
}
}
}
void afisare()
{
int i;
for(i=1;i<=nr;i++)
{
for(vector<int>::iterator it=q[i].begin();it!=q[i].end();it++)
printf("%d ", *it);
printf("\n");
}
}