Pagini recente » Cod sursa (job #1972997) | Cod sursa (job #2886792) | Cod sursa (job #1672900) | Cod sursa (job #1821139) | Cod sursa (job #686602)
Cod sursa(job #686602)
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
int N,M,i,j,x,y,c,lg,ST[200010],niv[100010],up[100010];
vector<int> G[100010],Q[100010];
void read(),solve(),dfs(int,int);
int main()
{
read();
solve();
return 0;
}
void read()
{
freopen("biconex.in","r",stdin);
freopen("biconex.out","w",stdout);
scanf("%d%d",&N,&M);
for(i=1;i<=M;i++)
{
scanf("%d%d",&x,&y);
G[x].push_back(y);
G[y].push_back(x);
}
}
void solve()
{
for(i=1;i<=N;i++)
if(!niv[i])
dfs(i,0);
printf("%d\n",c);
for(i=1;i<=c;i++)
{
for(vector<int>::iterator it=Q[i].begin();it!=Q[i].end();it++)
printf("%d ",*it);
printf("\n");
}
}
void dfs(int nod,int tata)
{
int vecin;
niv[nod]=up[nod]=niv[tata]+1;
for(vector<int>::iterator it=G[nod].begin();it!=G[nod].end();it++)
{
vecin=*it;
if(vecin==tata)continue;
if(!niv[vecin])
{
ST[++lg]=nod;
ST[++lg]=vecin;
dfs(vecin,nod);
up[nod]=min(up[nod],up[vecin]);
if(up[vecin]>=niv[nod])
{
for(i=lg-1,j=lg;;i-=2,j-=2)
if(ST[i]==nod&&ST[j]==vecin)
break;
sort(ST+i,ST+lg+1);
c++;
Q[c].push_back(ST[i]);
for(j=i+1;j<=lg;j++)
if(ST[j]!=ST[j-1])
Q[c].push_back(ST[j]);
lg=i-1;
}
}
else
up[nod]=min(up[nod],up[vecin]);
}
}