Pagini recente » Cod sursa (job #1497574) | Cod sursa (job #146294) | Cod sursa (job #3355002) | Cod sursa (job #219857) | Cod sursa (job #3346487)
#include <bits/stdc++.h>
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
vector <int> v[100009];
int niv[100009];
int stiva[200009], vf=0, low[200009];
int cnt=0;
vector <int> bcc[100009];
void dfs (int nod)
{
int x=nod;
stiva[++vf]=nod;
low[nod]=niv[nod];
for (auto y:v[nod])
{
if (niv[y])
low[x]=min (low[x], niv[y]);
else
{
niv[y]=niv[nod]+1;
dfs (y);
low[x]=min (low[x], low[y]);
if (low[y]>=niv[x])
{
cnt++;
while (stiva[vf]!=y)
bcc[cnt].push_back(stiva[vf--]);
//vf--;
bcc[cnt].push_back(stiva[vf--]);
bcc[cnt].push_back(x);
}
}
}
}
signed main ()
{
int n, m;
f >> n >> m;
for (int i=1; i<=m; i++)
{
int x, y;
f >> x >> y;
v[x].push_back(y);
v[y].push_back(x);
}
for (int i=1; i<=n; i++)
{
if (!niv[i])
{
niv[i]=1;
dfs(i);
}
}
g << cnt << '\n';
for (int i=1; i<=cnt; i++)
{
for (auto x:bcc[i])
g <<x<<' ';
g << '\n';
}
}