Pagini recente » Cod sursa (job #2410578) | Borderou de evaluare (job #2702912) | Cod sursa (job #2478479) | Cod sursa (job #2538017) | Cod sursa (job #3275187)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
//componentebiconexe
int n,m,niv[100001],minlv[100001],nr,pct;
bool artic[100001],viz[100001];
struct punte{
int x,y;
}punte[50001];
vector<int>v[100001],ccb[100001];
stack<int>sol;
void dfs(int k, int tata){
viz[k]=1;
sol.push(k);
niv[k]=minlv[k]=niv[tata]+1;
int fii=0;
for(auto i:v[k]){
if(viz[i]==1){
if(i!=tata) /// am muchie de intoarcere
minlv[k]=min(minlv[k],niv[i]);
}
else{
fii++;
dfs(i,k);
minlv[k]=min(minlv[k],minlv[i]);
if(niv[k]<=minlv[i]){
if(k!=1) /// pct de articulatie
artic[k]=1;
nr++;/// imi da comp biconexe
while(sol. top()!=k){
ccb[nr].push_back(sol. top());
sol.pop();
}
ccb[nr].push_back(k);
}
if(niv[k]<minlv[i]) { /// k i punte
punte[++pct]={k,i};
}
}
}
if(k==1&&fii>=2)
artic[k]=1;
}
int main()
{
int p;
// fin>>p;
p=1;
fin>>n>>m;
int x,y;
for(int i=1;i<=m;i++){
fin>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
dfs(1,0);
if(p==1){
fout<<nr<<'\n';
for(int i=1;i<=nr;i++){
/// fout<<ccb[i].size()<<" ";
for(auto j:ccb[i])
fout<<j<<" ";
fout<<'\n';
}
return 0;
}
if(p==2){
int nr=0;
for(int i=1;i<=n;i++)
if(artic[i])
nr++;
fout<<nr<<"\n";
for(int i=1;i<=n;i++)
if(artic[i]==1)
fout<<i<<" ";
return 0;
}
fout<<pct<<"\n";
for(int i=1;i<=pct;i++){
fout<<punte[i].x<<" "<<punte[i].y<<'\n';
}
return 0;
}