Pagini recente » Cod sursa (job #142810) | Cod sursa (job #2023817) | Cod sursa (job #2726787) | Cod sursa (job #1822165) | Cod sursa (job #2542106)
#include <bits/stdc++.h>
using namespace std;
ifstream in("biconex.in");
ofstream out("biconex.out");
const int Nmax = 1e5 + 5;
vector <int> adj[Nmax], solution[Nmax], niv, low;
stack < pair <int, int> > stiva;
int n, m, nocomp;
static inline void addsolution(int x, int y, int comp)
{
while(true)
{
int fir = stiva.top().first;
int sec = stiva.top().second;
stiva.pop();
solution[nocomp].push_back(fir);
solution[nocomp].push_back(sec);
if(fir == x && sec == y)
break;
}
sort(solution[comp].begin(), solution[comp].end());
}
static inline void dfs(int nod, int parent, int lvl)
{
niv[nod] = low[nod] = lvl;
for(auto i : adj[nod])
{
if(i == parent)
continue;
if(!niv[i])
{
stiva.push({nod, i});
dfs(i, nod, lvl + 1);
low[nod] = min(low[nod], low[i]);
if(niv[nod] <= low[i])
{
++ nocomp;
addsolution(nod, i, nocomp);
}
}
else
low[nod] = min(low[nod], niv[i]);
}
}
void output()
{
out << nocomp << '\n';
for(auto i = 1; i <= nocomp; ++ i)
{
for(auto& j : solution[i])
if(*(&j + 1) != j)
out << j << ' ';
out << '\n';
}
}
int main()
{
in.tie(0);
in >> n >> m;
niv.resize(n + 1);
low.resize(n + 1);
while(m --)
{
int x, y;
in >> x >> y;
adj[x].push_back(y);
adj[y].push_back(x);
}
dfs(1, 0, 1);
output();
return 0;
}