Pagini recente » Cod sursa (job #2320622) | Cod sursa (job #560444) | Cod sursa (job #2343096) | Cod sursa (job #2696328) | Cod sursa (job #1169418)
#include<iostream>
#include<fstream>
#include<vector>
#include<queue>
#include<cmath>
using namespace std;
void dfs(int x,vector <int> a[],vector <int> b[],vector <int> &viz,int **&d,int &it)
{
//cout<<x<<" ";
viz[x]=1;int i;
for(i=0;i<a[x].size();i++)
if (!viz[a[x][i]])
{ d[0][a[x][i]]=d[1][a[x][i]]=d[0][x]+1;
//cout<<x<<" "<<a[x][i]<<"\n";
dfs(a[x][i],a,b,viz,d,it);
//cout<<x<<"-"<<d[1][x]<<" "<<a[x][i]<<"-"<<d[1][a[x][i]]<<"\n";
if(d[1][x]>d[1][a[x][i]]) d[1][x]=d[1][a[x][i]];
//cout<<x<<" "<<a[x][i]<<"\n";
if(b[it].empty()) b[it].push_back(a[x][i]);
b[it].push_back(x);
if(d[0][x]<=d[1][a[x][i]]) it++;//cout<<x<<"\n";}
}
else if(abs(d[0][a[x][i]]-d[0][x])!=1)
{ if(d[0][a[x][i]]<d[0][x]&&d[0][a[x][i]]<d[1][x]) d[1][x]=d[0][a[x][i]];
else d[1][a[x][i]]=d[0][x];
}
}
int main()
{
ifstream f("biconex.in");
ofstream g("biconex.out");
int n,m,i,j,it=1;
f>>n>>m;
vector <int> a[n+1];
vector <int> b[n+1];
vector <int> viz(n+1,0);
int **d;
d=new int *[2];
d[0]=new int[n+1];
d[1]=new int[n+1];
for(i=1;i<=n;i++) d[0][i]=d[1][i]=0;
for(i=0;i<m;i++)
{ int x,y;f>>x>>y;
a[x].push_back(y);
a[y].push_back(x);
}
d[0][1]=d[1][1]=1;
dfs(1,a,b,viz,d,it);
//if(it-1==1)
for(i=0;i<=n;i++) viz[i]=0;
g<<it-1;
for(i=1;i<it;i++) {g<<'\n';
for(j=b[i].size()-1;j>=0;j--) if(viz[b[i][j]]!=i) {viz[b[i][j]]=i;g<<b[i][j]<<" ";}}
/*
for(i=1;i<=n;i++) cout<<i<<": "<<d[0][i]<<" "<<d[1][i]<<"\n";
cout<<'\n';
for(i=1;i<=n;i++)
{
cout<<i<<":";
for(j=0;j<a[i].size();j++) cout<<a[i][j]<<" ";
cout<<'\n';
}
*/
f.close();
return 0;
}