Pagini recente » Cod sursa (job #1250433) | Cod sursa (job #335719) | Cod sursa (job #2670037) | Cod sursa (job #2723302) | Cod sursa (job #2799796)
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream in("biconex.in");
ofstream out("biconex.out");
int n,m,x,y,nr;
vector<vector<int>>a,r;
queue<int>s;
bool v[100010],v2[100010];
struct noduri{int l,t;}nod[100010];
void arbore(int i)
{
bool p=false;
for(auto x:a[i])
{
if(v[x]==false)
{
p=true;
v[x]=true;
nod[x].l=nod[i].l+1;
nod[x].t=i;
arbore(x);
}
}
if(p==false)
s.push(i);
return;
}
int main()
{
in>>n>>m;
a.resize(n+5);
r.resize(n+5);
for(int i=1;i<=m;++i)
{
in>>x>>y;
a[x].push_back(y);
a[y].push_back(x);
}
nod[1].t=0;
nod[1].l=0;
for(int i=1;i<=n;++i)
{
if(v[i]==false)
{
v[i]=true;
arbore(i);
}
}
while(!s.empty())
{
int y=s.front(),nmin;
s.pop();
if(v2[y]==true||y==1)
continue;
nmin=nod[y].l;
++nr;
v2[y]=true;
for(auto x:a[y])
{
if(nmin>nod[x].l&&nod[x].l+1!=nod[y].l)
nmin=nod[x].l;
}
r[nr].push_back(y);
y=nod[y].t;
while(nmin<nod[y].l)
{
v2[y]=true;
r[nr].push_back(y);
for(auto x:a[y])
{
if(nmin>nod[x].l&&nod[x].l+1!=nod[y].l)
nmin=nod[x].l;
}
y=nod[y].t;
}
r[nr].push_back(y);
s.push(y);
}
out<<nr<<'\n';
for(int i=1;i<=nr;++i)
{
for(auto x:r[i])
out<<x<<' ';
out<<'\n';
}
return 0;
}