Pagini recente » Cod sursa (job #495911) | Borderou de evaluare (job #432810) | Cod sursa (job #2790193) | Cod sursa (job #2297022) | Cod sursa (job #2872865)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
const int MAX=1e5+5;
int n,m,a,b,tmp[MAX],lowtmp[MAX],part[MAX],viz[MAX],timp;
vector < int > v[MAX],sol1,sol2;
vector < pair < int, int > > mch;
vector < vector < int > > bicomp;
void DFS(int nod, int tata)
{
bool ispart=0;
int fii=0;
tmp[nod]=lowtmp[nod]=++timp;
for(auto vec : v[nod])
{
if(vec==tata)
continue;
if(!tmp[vec])
{
mch.push_back({nod,vec});
DFS(vec,nod);
lowtmp[nod]=min(lowtmp[nod],lowtmp[vec]);
if(tmp[nod]<=lowtmp[vec])
{
vector < int > comp;
do
{
a=mch.back().first;
b=mch.back().second;
mch.pop_back();
comp.push_back(a);
comp.push_back(b);
} while(a!=nod || b!=vec);
sort(comp.begin(),comp.end());
comp.erase(unique(comp.begin(),comp.end()),comp.end());
bicomp.push_back(comp);
}
}
else
lowtmp[nod]=min(lowtmp[nod],tmp[vec]);
}
}
int main()
{
fin >> n >> m;
while(m--)
{
fin >> a >> b;
v[a].push_back(b);
v[b].push_back(a);
}
DFS(1,0);
fout << bicomp.size() << '\n';
for(auto comp : bicomp)
{
for(auto elem : comp)
fout << elem << " ";
fout << '\n';
}
return 0;
}