Pagini recente » Cod sursa (job #46872) | Cod sursa (job #2390486) | Cod sursa (job #1006654) | Cod sursa (job #2399803) | Cod sursa (job #2323619)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");
int n,m,i,x,y;
vector <int> vec[1000];
vector <int> sol,stiv;
struct per{int x,y;}aux;
vector <per> muc;
vector <int> comp[1000];
int nrcomp;
int niv[1000],nma[1000],nr1;
void dfs(int x)
{
nma[x]=niv[x];
stiv.push_back(x);
for(int i:vec[x])
{
if(niv[i]==0)
{
if(x==1)
nr1++;
niv[i]=niv[x]+1;
dfs(i);
nma[x]=min(nma[x],nma[i]);
if(niv[x]<=nma[i]&&x!=1)
{
nrcomp++;
while(stiv.back()!=i)
{
comp[nrcomp].push_back(stiv.back());
stiv.pop_back();
}
comp[nrcomp].push_back(stiv.back());
stiv.pop_back();
sol.push_back(i);
comp[nrcomp].push_back(x);
}
if(niv[x]<nma[i])
{
aux.x=x;
aux.y=i;
muc.push_back(aux);
}
}
else
if(niv[x]!=niv[i]+1)
nma[x]=min(nma[x],niv[i]);
}
}
int main()
{
fin>>n>>m;
for(i=1;i<=m;i++)
{
fin>>x>>y;
vec[x].push_back(y);
vec[y].push_back(x);
}
niv[1]=1;
dfs(1);
nrcomp++;
while(!stiv.empty())
{
comp[nrcomp].push_back(stiv.back());
stiv.pop_back();
}
if(nr1>1)
sol.push_back(1);
fout<<nrcomp<<'\n';
for(i=1;i<=nrcomp;i++)
{
sort(comp[i].begin(),comp[i].end());
for(int z:comp[i])
{
fout<<z<<" ";
}
fout<<'\n';
}
while(!muc.empty())
{
fout<<muc.back().x<<" "<<muc.back().y<<'\n';
muc.pop_back();
}
while(!sol.empty())
{
fout<<sol.back()<<'\n';
sol.pop_back();
}
return 0;
}