#include <bits/stdc++.h>
using namespace std;
void dfs(int node, int start, int& timeCounter, vector<vector<int>>& Dsachke, vector<int>& Found, vector<int>& Lowest, vector<pair<int, int>>& BRIDGES) {
Found[node] = Lowest[node] = timeCounter++;
cout << "Đang thăm node: " << node << ", timeCounter: " << timeCounter << ", Found[" << node << "]: " << Found[node] << ", Lowest[" << node << "]: " << Lowest[node] << endl;
for (int neighbor : Dsachke[node]) {
if (neighbor == start) {
continue; // Bỏ qua đỉnh cha
}
if (Found[neighbor] != -1) { // Đỉnh đã được thăm
Lowest[node] = min(Lowest[node], Found[neighbor]);
cout << "Thăm lại neighbor: " << neighbor << ", Found[" << neighbor << "]: " << Found[neighbor] << ", cập nhật Lowest[" << node << "]: " << Lowest[node] << endl;
}
else { // Đỉnh chưa được thăm
dfs(neighbor, node, timeCounter, Dsachke, Found, Lowest, BRIDGES);
Lowest[node] = min(Lowest[node], Lowest[neighbor]);
cout << "Quay lại từ neighbor: " << neighbor << ", cập nhật Lowest[" << node << "]: " << Lowest[node] << endl;
if (Lowest[neighbor] > Found[node]) {
// Cạnh (node, neighbor) là cầu
BRIDGES.push_back({node, neighbor});
cout << "Cầu tìm thấy: " << node << " - " << neighbor << endl;
}
}
}
}
int main() {
int numberOfNodes, numberOfEdges, timeCounter = 0; // Số đỉnh, số cạnh và bộ đếm thời gian
cin >> numberOfNodes >> numberOfEdges;
// số node, số cạnh
vector<vector<int>> Dsachke(numberOfNodes + 1); // Danh sách kề của đồ thị
vector<int> Found(numberOfNodes + 1, -1); // Thời gian khám phá
vector<int> Lowest(numberOfNodes + 1, -1); // Thời gian thấp nhất
vector<pair<int, int>> BRIDGES; // Danh sách cầu
for (int i = 0; i < numberOfEdges; i++) {
int a, b; // Thay nodeA, nodeB bằng a, b cho dễ hiểu
cin >> a >> b;
Dsachke[a].push_back(b);
Dsachke[b].push_back(a);
}
// phần này dùng để nhập danh sách kề từ input
for (int node = 1; node <= numberOfNodes; node++) {
if (Found[node] == -1) {
dfs(node, -1, timeCounter, Dsachke, Found, Lowest, BRIDGES);
}
}
// cái này đơn giản là để nếu đồ thị bị phân ra thành n thành phần liên thông thì lệnh có thể kiểm tra từng thành phần liên thông đó
cout << "Số cầu: " << BRIDGES.size() << endl;
for (auto bridge : BRIDGES) {
cout << bridge.first << " - " << bridge.second << endl;
}
// In ra các biến quan trọng
cout << "\nKết quả biến Found: ";
for (int i = 1; i <= numberOfNodes; i++) {
cout << Found[i] << " ";
}
cout << "\nKết quả biến Lowest: ";
for (int i = 1; i <= numberOfNodes; i++) {
cout << Lowest[i] << " ";
}
cout << "\nGiá trị cuối cùng của timeCounter: " << timeCounter << endl;
return 0;
}
