难题求救
  • 板块灌水区
  • 楼主Aussicer
  • 当前回复3
  • 已保存回复3
  • 发布时间2024/3/3 17:27
  • 上次更新2024/3/3 17:35:30
查看原帖
难题求救
1061023
Aussicer楼主2024/3/3 17:27

请找出一个带有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;

}

2024/3/3 17:27
加载中...