Pagini recente » Monitorul de evaluare | Profil Pintilie_Andrei | Profil LazarAndrei | Rating Toma Adrian (aditoma2001) | Cod sursa (job #2263791)
#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], 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].push_back(a);
sol[nr].push_back(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++) {
sort(sol[i].begin(), sol[i].end());
const int n = (int)sol[i].size();
g << sol[i][0] << " ";
for (int j = 1; j < n; j++) {
if (sol[i][j] != sol[i][j - 1])
g << sol[i][j] << " ";
}
g << '\n';
}
g.close();
return 0;
}