Pagini recente » Cod sursa (job #1575480) | Cod sursa (job #2598732) | Cod sursa (job #2308248) | Cod sursa (job #1832406) | Cod sursa (job #1394680)
#include <fstream>
#include <vector>
#include <stack>
#include <cstring>
using namespace std;
const int kMaxN = 100005;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int N, M;
vector<int> G[kMaxN];
bool use[kMaxN];
int level[kMaxN], low[kMaxN];
stack<int> st;
vector<vector<int>> sol;
void AddComponent(int node, int son) {
vector<int> crt;
while (st.top() != son) {
crt.push_back(st.top());
st.pop();
}
st.pop();
crt.push_back(son);
crt.push_back(node);
sol.push_back(crt);
}
void DFS(int node, int padre) {
use[node] = true;
for (int i : G[node]) {
if (i == padre)
continue;
if (use[i]) {
low[node] = min(low[node], level[i]);
} else {
st.push(i);
level[i] = level[node] + 1;
DFS(i, node);
low[node] = min(low[node], low[i]);
if (!padre || low[i] >= level[node])
AddComponent(node, i);
}
}
}
int main() {
fin >> N >> M;
while (M--) {
int x, y;
fin >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
memset(low, 0x3f, sizeof low);
for (int i = 1; i <= N; ++i)
if (!use[i])
DFS(i, 0);
fout << sol.size() << "\n";
for (const auto &crt : sol) {
for (int i : crt)
fout << i << " ";
fout << "\n";
}
return 0;
}