Pagini recente » Cod sursa (job #546309) | Cod sursa (job #3179821) | Cod sursa (job #3233154) | Cod sursa (job #46601) | Cod sursa (job #2908777)
#include <bits/stdc++.h>
#define N 100005
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int task,n,m,nivel[N],nma[N],nrb,root;
bool viz[N],critic[N];
vector<int>g[N],biconexe[N];
struct muchie
{
int x,y;
};
vector<muchie>punti;
stack<int>stv;
void DFS(int nod,int tata)
{
viz[nod]=1;
stv.push(nod);
nivel[nod]=nivel[tata]+1;
nma[nod]=nivel[nod];
for(auto x:g[nod])
if(x!=tata)
if(viz[x]) nma[nod]=min(nma[nod],nivel[x]);
else
{
DFS(x,nod);
nma[nod]=min(nma[nod],nma[x]);
if(nivel[nod]<=nma[x] && nod!=root)
critic[nod]=1;
if(nivel[nod]<nma[x]) punti.push_back({nod,x});
if(nivel[nod]<=nma[x])
{
++nrb;
while(stv.top()!=x)
biconexe[nrb].push_back(stv.top()),stv.pop();
biconexe[nrb].push_back(x);
stv.pop();
biconexe[nrb].push_back(nod);
}
}
}
int main()
{
int i,j,x,y;
task=1;
fin>>n>>m;
for(i=1;i<=m;i++) fin>>x>>y,g[x].push_back(y),g[y].push_back(x);
root=1;
DFS(root,0);
if(task==1)
{
fout<<nrb<<"\n";
for(i=1;i<=nrb;i++)
{
//fout<<biconexe[i].size()<<" ";
for(auto x:biconexe[i]) fout<<x<<" ";
fout<<"\n";
}
}
else if(task==2)
{
bool ok=0;
int nrc=0;
for(i=1;i<=n;i++)
if(nivel[i]==2)
if(!ok) ok=1;
else {critic[1]=1;break;}
fout<<count(critic+1,critic+n+1,1)<<"\n";
for(i=1;i<=n;i++)
if(critic[i]) fout<<i<<" ";
}
else
{
fout<<punti.size()<<"\n";
for(auto k:punti) fout<<k.x<<" "<<k.y<<"\n";
}
return 0;
}