Pagini recente » Cod sursa (job #3341433) | Cod sursa (job #3334903) | Cod sursa (job #3341098) | Cod sursa (job #3315724) | Cod sursa (job #3332373)
#include <bits/stdc++.h>
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
const int NMAX = 100001;
struct muchie
{
int x,y;
muchie(int xx=0, int yy=0)
{
x=xx, y=yy;
}
};
int P,N,M,nrFii, nrCB,
Niv[NMAX], Nma[NMAX],
S[NMAX],vf;
vector<int> G[NMAX],CB[NMAX];
vector<muchie> MC;
set<int> PA;
bool viz[NMAX];
void citire()
{
int x,y;
f>>N>>M;P=1;
for(int i=1;i<=M;++i)
{
f>>x>>y;
G[x].push_back(y);
G[y].push_back(x);
}
}
void DFSpa(int x, int tata)
{
viz[x]=1;
Niv[x]=Niv[tata]+1;
Nma[x]=Niv[x];
for(const auto &y: G[x])
{
if(y==tata) continue;
if(viz[y])
Nma[x] = min(Nma[x], Niv[y]);
else
{
DFSpa(y,x);
Nma[x]=min(Nma[x],Nma[y]);
if(x==1)
nrFii++;
else
{
if(Niv[x]<=Nma[y])
PA.insert(x);
}
}
}
}
void DFScb(int x, int tata)
{
S[++vf]=x;
viz[x]=1;
Niv[x]=Niv[tata]+1;
Nma[x] = Niv[x];
for(const auto &y:G[x])
{
if(y==tata)continue;
if(viz[y])
Nma[x] = min(Nma[x],Niv[y]);
else
{
DFScb(y,x);
Nma[x] = min(Nma[x],Nma[y]);
if(Niv[x]<=Nma[y])
{
++nrCB;
while(S[vf]!=y)
CB[nrCB].push_back(S[vf--]);
CB[nrCB].push_back(y);
--vf;
CB[nrCB].push_back(x);
}
}
}
}
void DFSmc(int x, int tata)
{
viz[x]=1;
Niv[x]=Niv[tata]+1;
Nma[x]=Niv[x];
for(const auto &y: G[x])
{
if(y==tata) continue;
if(viz[y])
Nma[x]=min(Nma[x], Niv[y]);
else
{
DFSmc(y,x);
Nma[x]=min(Nma[x],Nma[y]);
if(Niv[x]<Nma[y])
MC.push_back(muchie(x,y));
}
}
}
int main()
{
citire();
switch(P)
{
case 1:
DFScb(1,0);
g<<nrCB<<'\n';
for(int i=1; i<= nrCB; ++i)
{
//g<<CB[i].size()<<' ';
for(const auto &x: CB[i])
g<<x<<' ';
g<<'\n';
}
break;
case 2:
DFSpa(1,0);
if(nrFii>=2) PA.insert(1);
g<<PA.size()<< '\n';
for(const auto &x:PA)
g<<x<<' ';
break;
case 3:
DFSmc(1,0);
g<<MC.size()<<'\n';
for(const auto &m:MC)
g<<m.x<<' '<<m.y<<'\n';
}
return 0;
}