Pagini recente » Cod sursa (job #1427248) | Cod sursa (job #3032925) | Cod sursa (job #1378429) | Cod sursa (job #1740780) | Cod sursa (job #1028449)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
vector <int> v[100001];
int n,m,cost[100001],t[100001],pc[200001],po[200001],k,afis[100001],nr,mat[500][10001],nivel[100001];
ofstream out("biconex.out");
void showtime()
{
for(int i=0; i<k; i++)
{
if(pc[i]!=0)
{
nr++;
mat[nr][0]=pc[i];
mat[nr][1]=po[i];
}
}
}
void dfs(int nod)
{
for(int i=0; i<v[nod].size(); i++)
{
if(cost[v[nod][i]]==1 && nivel[v[nod][i]]<nivel[nod]-1)
{
nr++;
int z=0,j;
for( j=k-1; pc[j]!=v[nod][i]; j--)
{
afis[z]=po[j];
po[j]=0;
pc[j]=0;
z++;
}
afis[z++]=pc[j]; pc[j]=0;
afis[z++]=po[j]; po[j]=0;
sort(afis, afis+z);
for(int x=0; x<z; x++)
mat[nr][x]=afis[x];
for(int x=0; x<z; x++)
afis[x]=0;
}else
if(cost[v[nod][i]]==0)
{
nivel[v[nod][i]]=nivel[nod]+1;
cost[v[nod][i]]=1;
pc[k]=nod;
po[k]=v[nod][i];
k++;
t[v[nod][i]]=nod;
dfs(v[nod][i]);
}
}
}
int main()
{
ifstream in("biconex.in");
int i,j,x,y;
in>>n>>m;
for(i=0; i<m; i++)
{
in>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
in.close();
cost[1]=1;
nivel[1]=1;
dfs(1);
showtime();
out<<nr<<endl;
for(i=1; i<=nr; i++)
{
j=0;
while(mat[i][j]!=0)
{
out<<mat[i][j]<<" ";
j++;
}
out<<endl;
}
out.close();
return 0;
}