Pagini recente » Cod sursa (job #2975115) | Cod sursa (job #655181) | Cod sursa (job #1221934) | Cod sursa (job #949257) | Cod sursa (job #2871168)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
const string filename = "biconex";
ifstream fin(filename + ".in");
ofstream fout(filename + ".out");
const int maxN = 100005;
int n, m, depth[maxN], max_sus[maxN];
vector <int> G[maxN];
vector <pair <int, int>> muchii;
vector <int> comp;
vector <vector <int>> bicomp;
void dfs(int nod, int sus)
{
depth[nod] = depth[sus] + 1;
max_sus[nod] = depth[nod];
for(int vecin : G[nod])
{
if(vecin == sus)
continue;
if(depth[vecin] == 0)
{
muchii.push_back({nod, vecin});
dfs(vecin, nod);
max_sus[nod] = min(max_sus[nod], max_sus[vecin]);
if(max_sus[vecin] >= depth[nod])
{
int x, y;
do
{
x = muchii.back().first, y = muchii.back().second;
muchii.pop_back();
comp.push_back(x), comp.push_back(y);
}
while(x != nod || y != vecin);
sort(comp.begin(), comp.end());
comp.erase(unique(comp.begin(), comp.end()), comp.end());
bicomp.push_back(comp);
comp.clear();
}
}
else
max_sus[nod] = min(max_sus[nod], depth[vecin]);
}
}
int main()
{
fin >> n >> m;
for(int i = 1; i <= m; i++)
{
int x, y;
fin >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
dfs(1, 0);
fout << bicomp.size() << '\n';
for(auto c : bicomp)
{
for(int elem : c)
fout << elem << ' ';
fout << '\n';
}
return 0;
}