Pagini recente » Cod sursa (job #394027) | Cod sursa (job #256690) | Cod sursa (job #674656) | Cod sursa (job #2380882) | Cod sursa (job #1344096)
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int MAXN = 100000;
int grad[MAXN + 1];
bool viz[MAXN + 1];
vector <int> drum[MAXN + 1],nod_art,rez[MAXN + 1];
int top,st[MAXN + 1000];
int n,m,cnt;
void rezolva(int stop)
{
int temp;
while(st[top] != stop && top != 0)
{
temp=st[top];
rez[cnt].push_back(temp);
top--;
}
rez[cnt].push_back(stop);
cnt++;
}
int dfs(int tata,int last)
{
int fiu,i,temp,ret=grad[tata];
viz[tata]=1;
st[++top]=tata;
if(drum[tata].size()==1)
ret=grad[last];
else
{
for(i=0;i<drum[tata].size();i++)
{
fiu=drum[tata][i];
if(fiu!=last)
{
if(viz[fiu]==0)
{
grad[fiu]=grad[tata]+1;
temp=dfs(fiu,tata);
if(temp==grad[tata])
{
nod_art.push_back(tata);
rezolva(tata);
}
ret=min(ret,temp);
}
else
{
ret=min(ret,grad[fiu]);
}
}
}
}
return ret;
}
int main()
{
int i,j,x,y;
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);
drum[x].push_back(y);
drum[y].push_back(x);
}
grad[1]=1;
dfs(1,0);
if(top!=0)
rezolva(1);
printf("%d\n",cnt);
for(i=0;i<cnt;i++)
{
sort(rez[i].begin() , rez[i].end());
for(j=0;j<rez[i].size();j++)
printf("%d ",rez[i][j]);
printf("\n");
}
return 0;
}