Pagini recente » Cod sursa (job #177182) | Cod sursa (job #2786663) | Cod sursa (job #1886767) | Cod sursa (job #1099719) | Cod sursa (job #2324399)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int n,m,i,x,y;
vector <int> vec[100005];
vector <int> sol,stiv;
struct per{int x,y;}aux;
vector <per> muc;
vector <int> comp[100005];
int nrcomp;
int niv[100005],nma[100005],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)
{
sol.push_back(x);
}
if(niv[x]<=nma[i])
{
nrcomp++;
while(stiv.back()!=i)
{
comp[nrcomp].push_back(stiv.back());
stiv.pop_back();
}
comp[nrcomp].push_back(stiv.back());
stiv.pop_back();
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]);
}
}
void afisArticulatii()
{
fout<<sol.size()<<'\n';
while(!sol.empty())
{
fout<<sol.back()<<'\n';
sol.pop_back();
}
}
void afisPunti()
{
fout<<muc.size()<<'\n';
while(!muc.empty())///afisare muchiii
{
fout<<muc.back().x<<" "<<muc.back().y<<'\n';
muc.pop_back();
}
}
void afisComponente()
{
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';
}
}
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);
if(nr1>1)
sol.push_back(1);
afisComponente();
return 0;
}