Pagini recente » Cod sursa (job #308257) | Cod sursa (job #3154962) | Cod sursa (job #217132) | Cod sursa (job #2957559) | Cod sursa (job #1345291)
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int MAXN = 100000;
int h[MAXN + 1];
int ret[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++;
}
void dfs(int tata,int last)
{
int fiu,i,temp,cr=0;
h[tata]=h[last]+1;
ret[tata]=h[tata];
viz[tata]=1;
st[++top]=tata;
for(i=0;i<drum[tata].size();i++)
{
fiu=drum[tata][i];
if(fiu!=last)
{
if(viz[fiu]==0)
{
cr++;
if(cr>1)
st[++top]=tata;
dfs(fiu,tata);
if(ret[fiu]>=h[tata] && last!=0)
{
nod_art.push_back(tata);
rezolva(tata);
}
ret[tata]=min(ret[tata],ret[fiu]);
}
else
{
ret[tata]=min(ret[tata],h[fiu]);
}
}
}
if(cr>1 && last==0)
{
nod_art.push_back(tata);
rezolva(tata);
}
}
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);
}
h[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());
rez[i].resize(unique(rez[i].begin(),rez[i].end()) - rez[i].begin());
for(j=0;j<rez[i].size();j++)
printf("%d ",rez[i][j]);
printf("\n");
}
return 0;
}