Pagini recente » Cod sursa (job #1791669) | Cod sursa (job #969137) | Cod sursa (job #716296) | Cod sursa (job #2868613) | Cod sursa (job #1241030)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
struct vec
{ int x,y;} st[200005];
int n,m,k,use[100005],niv[100005],mn[100005],inf=2147000000,nrc,sol[100005];
vector <int> v[100005],c[200005];
void DFS(int x)
{ int i,y;
use[x]=1;mn[x]=niv[x];
for(i=0;i<v[x].size();i++)
{ y=v[x][i];
if (use[y]) continue;
use[y]=1;
k++; st[k].x=x; st[k].y=y;
niv[y]=niv[x]+1;
DFS(y);
mn[x]=min(mn[x],mn[y]);
if (mn[x]>=niv[x])
{ nrc++;
while(!(st[k].x==x && st[k].y==y))
{c[nrc].push_back(st[k].x);
c[nrc].push_back(st[k].y);
k--;}
c[nrc].push_back(st[k].x);
c[nrc].push_back(st[k].y);
k--;
}
}
for(i=0;i<v[x].size();i++)
{ y=v[x][i];
if (niv[y]<niv[x]-1) mn[x]=min(mn[x],niv[y]);
}
}
int main()
{ int i,j,x,y,p;
f>>n>>m;
for(i=1;i<=m;i++)
{ f>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
for(i=1;i<=n;i++)
if (!use[i]) DFS(i);
g<<nrc<<"\n";
for(i=1;i<=nrc;i++)
{sort(c[i].begin(),c[i].end());
p=0;
for(j=0;j<c[i].size();j++)
if (!j || c[i][j]!=c[i][j-1])
{p++; sol[p]=c[i][j];}
for(j=1;j<=p;j++)
g<<sol[j]<<" ";
g<<"\n";
}
return 0;
}