Pagini recente » Cod sursa (job #2692547) | Cod sursa (job #3329936) | Cod sursa (job #934607) | Cod sursa (job #1825211) | Cod sursa (job #3307426)
#include <bits/stdc++.h>
#define int long long
using namespace std;
ifstream fin ("biconex.in");
ofstream fout ("biconex.out");
const int nmax = 1e5 + 5;
stack <int> st;
vector <int> v[nmax];
vector <vector <int>> bcc;
int n, m, lvl[nmax], lowlink[nmax];
void add_bcc (int x, int nod) //muchie critica
{
vector <int> v{nod};
int vf;
do
{
vf = st.top ();
st.pop ();
v.push_back (vf);
}
while (vf != x);
bcc.push_back (v);
}
void dfs (int nod, int parent)
{
st.push (nod);
lvl[nod] = lvl[parent] + 1;
lowlink[nod] = lvl[nod];
for (auto x : v[nod])
{
if (x == parent)
continue;
if (lvl[x] == 0)
{
dfs (x, nod);
if (lowlink[x] >= lvl[nod]) //nod este nod critic
add_bcc (x, nod);
lowlink[nod] = min (lowlink[nod], lowlink[x]);
}
else //muchie de intoarcere
lowlink[nod] = min (lowlink[nod], lvl[x]);
}
}
signed main ()
{
fin >> n >> m;
for (int i = 1; i <= m; i++)
{
int x, y;
fin >> x >> y;
v[x].push_back (y);
v[y].push_back (x);
}
dfs (1, 0);
fout << bcc.size () << '\n';
for (auto comp : bcc)
{
for (auto node : comp)
fout << node << ' ';
fout << '\n';
}
}