Pagini recente » Cod sursa (job #3147068) | Cod sursa (job #1247338) | Cod sursa (job #85009) | Cod sursa (job #383783) | Cod sursa (job #1371132)
#include <fstream>
#include <iostream>
#include <set>
#include <vector>
using namespace std;
ifstream fin ("biconex.in");
ofstream fout ("biconex.out");
const int N = 1e5 + 5;
vector <int> g[N];
vector <pair <int, int> > st;
set <int> comp[N];
int n, m, c, lo[N], niv[N];
void remove(int x, int y) {
pair <int, int> crt;
do {
crt = st.back();
st.pop_back();
comp[c].insert(crt.first);
comp[c].insert(crt.second);
} while (crt.first != x || crt.second != y);
c++;
}
void dfs(int x, int tata, int l) {
//cout << x << "\n" << flush;
lo[x] = niv[x] = l;
for (vector <int> :: iterator it = g[x].begin(); it != g[x].end(); ++it) {
if (*it == tata)
continue;
if (!niv[*it]) {
st.push_back(make_pair (x, *it));
dfs(*it, x, l + 1);
lo[x] = min(lo[x], lo[*it]);
if (lo[*it] >= niv[x])
remove(x, *it);
}
else
lo[x] = min(lo[x], niv[*it]);
}
}
int main() {
fin >> n >> m;
for (int x, y, i = 0; i < m; ++i) {
fin >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
}
dfs(1, 0, 1);
fout << c << "\n";
for (int i = 0; i < c; ++i) {
for (set <int> :: iterator it = comp[i].begin(); it != comp[i].end(); ++it)
fout << *it << " ";
fout << "\n";
}
}