Pagini recente » Cod sursa (job #727554) | Cod sursa (job #2476418) | Cod sursa (job #1319863) | Cod sursa (job #2796381) | Cod sursa (job #3120419)
/*
Lefter Sergiu - 06/04/2023
*/
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream in("biconex.in");
ofstream out("biconex.out");
const int N = 1e5;
stack<int> stiva;
vector<vector<int>> cbc;
vector<int> a[N + 1];
int t_in[N + 1], t_min[N + 1], timp;
void adauga_cbc(int x, int y, vector<int> &c) {
while (stiva.top() != y) {
c.push_back(stiva.top());
stiva.pop();
}
c.push_back(y);
stiva.pop();
c.push_back(x);
}
void DFS(int x, int t) {
t_min[x] = t_in[x] = ++timp;
stiva.push(x);
for (auto y: a[x]) {
if (y == t) {
continue;
}
if (t_in[y] == 0) { //y e fiu al lui x in arborele DFS
DFS(y, x);
t_min[x] = min(t_min[x], t_min[y]);
if (t_min[y] >= t_in[x]) {
vector<int> c;
adauga_cbc(x, y, c);
cbc.push_back(c);
}
}
else { //y este ascendent (dar nu tata) al lui x in arborele DFS
t_min[x] = min(t_min[x], t_in[y]);
}
}
}
int main() {
int n, m;
in >> n >> m;
for (int i = 0; i < m; i++) {
int x, y;
in >> x >> y;
a[x].push_back(y);
a[y].push_back(x);
}
for (int i = 1; i <= n; i++) {
if (t_in[i] == 0) {
DFS(i, 0);
}
}
out << cbc.size() << '\n';
for (auto c: cbc) {
for (auto x: c) {
out << x << " ";
}
out << "\n";
}
in.close();
out.close();
return 0;
}