Pagini recente » Cod sursa (job #3293624) | Cod sursa (job #2485835) | Cod sursa (job #3121769) | Cod sursa (job #143927) | Cod sursa (job #2263790)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>
#include <set>
#include <stdio.h>
using namespace std;
#define NMAX 100001
vector <int> v[NMAX];
set <int> sol[2 * NMAX];
int viz[NMAX], low[NMAX], lev[NMAX], nr;
stack <pair <int, int> > st;
void bc(int nod, int x) {
int a, b;
nr++;
do {
a = st.top().first;
b = st.top().second;
sol[nr].insert(a);
sol[nr].insert(b);
st.pop();
} while (a != nod || x != b);
}
void dfs(int nod, int niv, int p) {
viz[nod] = 1;
lev[nod] = niv;
low[nod] = niv;
for (const int x : v[nod]) {
if (viz[x] == 0) {
st.push(make_pair(nod, x));
dfs(x, niv + 1, nod);
low[nod] = min(low[nod], low[x]);
if (low[x] >= niv) {
bc(nod, x);
}
} else if (x != p) {
low[nod] = min(low[nod], lev[x]);
}
}
}
int main()
{
ios::sync_with_stdio(false);
int n, m;
ifstream f("biconex.in");
ofstream g("biconex.out");
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);
}
f.close();
for (int i = 1; i <= n; i++) {
if (viz[i] == 0)
dfs(i, 0, 0);
}
g << nr << '\n';
for (int i = 1; i <= nr; i++) {
for (const int x : sol[i]) {
g << x << " ";
}
g << '\n';
}
g.close();
return 0;
}