Pagini recente » Cod sursa (job #3285776) | Cod sursa (job #3286659) | Cod sursa (job #3229340) | Cod sursa (job #3293078) | Cod sursa (job #2263796)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;
#define NMAX 100001
vector <int> v[NMAX];
vector <vector <int> > sol;
int low[NMAX], lev[NMAX];
short viz[NMAX];
stack <pair <int, int> > st;
void bc(int nod, int x) {
int a, b;
vector <int> v;
do {
a = st.top().first;
b = st.top().second;
v.push_back(a);
v.push_back(b);
st.pop();
} while (a != nod || x != b);
sol.push_back(v);
}
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 << sol.size() << '\n';
for (vector <int>& v : sol) {
sort(v.begin(), v.end());
const int n = (int)v.size();
g << v[0] << " ";
for (int j = 1; j < n; j++) {
if (v[j] != v[j - 1])
g << v[j] << " ";
}
g << '\n';
}
g.close();
return 0;
}