请找出一个带有N个节点和M条边的无向图的所有双连通分量。双连通分量指的是一个最小的子图,删除其中任意一个顶点都不会影响整个子图的连通性。要求编写C++代码实现,使用Tarjan算法或其他相关算法来解决问题。```c #include #include #include #include
using namespace std;
const int MAXN = 100005;
vector adj[MAXN]; int low[MAXN], disc[MAXN], parent[MAXN]; bool visited[MAXN]; stack<pair<int, int>> bridgeStack; int discTime = 0;
void dfs(int u) { visited[u] = true; disc[u] = low[u] = ++discTime;
for (int v : adj[u]) {
if (!visited[v]) {
parent[v] = u;
dfs(v);
low[u] = min(low[u], low[v]);
if (low[v] > disc[u]) {
bridgeStack.push(make_pair(u, v));
}
} else if (v != parent[u]) {
low[u] = min(low[u], disc[v]);
}
}
}
void findBridges(int N) { for (int i = 0; i < N; ++i) { if (!visited[i]) { dfs(i); } } }
int main() { int N, M; cin >> N >> M;
for (int i = 0; i < M; ++i) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
findBridges(N);
cout << "Bridges in the graph:" << endl;
while (!bridgeStack.empty()) {
cout << bridgeStack.top().first << " " << bridgeStack.top().second << endl;
bridgeStack.pop();
}
return 0;
}