Pagini recente » Cod sursa (job #3287389) | Cod sursa (job #1541682) | Cod sursa (job #3222113) | Cod sursa (job #2469363) | Cod sursa (job #3192608)
#include <bits/stdc++.h>
#define mp make_pair
using namespace std;
const int NR = 100005;
ofstream out("biconex.out");
vector < int > v[NR];
vector < pair < int, int > > st;
int n, m, lvl[NR], lowest[NR];
vector < vector < int > > ans;
void make_cb(int x, int y) {
vector < int > c;
int cx, cy;
do {
cx = st.back().first;
cy = st.back().second;
st.pop_back();
c.push_back(cx), c.push_back(cy);
} while (!(cx == x && cy == y));
ans.push_back(c);
}
void dfs(int nod, int father) {
vector < int > ::iterator it;
lowest[nod] = lvl[nod];
for (it = v[nod].begin(); it != v[nod].end(); ++it) {
if (*it == father) continue;
if (!lvl[*it]) {
lvl[*it] = lvl[nod] + 1;
st.push_back(mp(nod, *it));
dfs(*it, nod);
lowest[nod] = min(lowest[nod], lowest[*it]);
if (lowest[*it] == lvl[nod]) make_cb(nod, *it);
}
else {
lowest[nod] = min(lowest[nod], lvl[*it]);
}
}
}
class InParser {
private:
FILE* fin;
char* buff;
int sp;
char read_ch() {
++sp;
if (sp == 4096) {
sp = 0;
fread(buff, 1, 4096, fin);
}
return buff[sp];
}
public:
InParser(const char* nume) {
fin = fopen(nume, "r");
buff = new char[4096]();
sp = 4095;
}
InParser& operator >> (int& n) {
char c;
while (!isdigit(c = read_ch()) && c != '-');
int sgn = 1;
if (c == '-') {
n = 0;
sgn = -1;
}
else {
n = c - '0';
}
while (isdigit(c = read_ch())) {
n = 10 * n + c - '0';
}
n *= sgn;
return *this;
}
InParser& operator >> (long long& n) {
char c;
n = 0;
while (!isdigit(c = read_ch()) && c != '-');
long long sgn = 1;
if (c == '-') {
n = 0;
sgn = -1;
}
else {
n = c - '0';
}
while (isdigit(c = read_ch())) {
n = 10 * n + c - '0';
}
n *= sgn;
return *this;
}
};
int main() {
InParser in("biconex.in");
int x, y, a, b;
in >> n >> m;
lvl[1] = 1;
while (m--) {
in >> x >> y;
v[x].push_back(y);
v[y].push_back(x);
}
dfs(1, 0);
a = ans.size();
out << a << '\n';
for (size_t i = 0; i < a; ++i, out << '\n') {
sort(ans[i].begin(), ans[i].end());
ans[i].erase(unique(ans[i].begin(), ans[i].end()), ans[i].end());
b = ans[i].size();
for (size_t j = 0; j < b; ++j) out << ans[i][j] << ' ';
}
}