C++ 代码优化与错误修复：计算无向图的连通分量

#pragma GCC optimize(1) #pragma GCC optimize(2) #pragma GCC optimize(3,'Ofast','inline') #include<bits/stdc++.h> using namespace std; inline static const nullptr_t _={ ios::sync_with_stdio(0); cin.tie(nullptr),cout.tie(nullptr); return nullptr; }(); int n,m,ans;vector g[10005]; bitset<10005> vis;

void dfs(int i){ for(int j=0;j<g[i].size();j++){ if(!vis[g[i][j]]){ vis[g[i][j]]=1; dfs(g[i][j]); } } }

int main(){ cin>>n>>m; for(int i=1;i<=m;i++){ int u,v; cin>>u>>v; g[u].emplace_back(v); g[v].emplace_back(u); } for(int i=1;i<=n;i++){ if(!vis[i]){ vis[i]=1; dfs(i); ans++; } } cout<<ans<<'\n'; return 0; }//答案错误，n和m<=10000

该代码旨在查找无向图中的连通分量数量。但是，代码中存在一些问题。

1. 在 dfs 函数中，循环错误地递增了 i 而不是 j。这会导致无限循环和错误的行为。

2. dfs 函数中的循环应该遍历当前节点 i 的邻居，而不是一直到 g[i].size()。正确的条件应该是 j < g[i].size()。

以下是修改后的代码：

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,'Ofast','inline')
#include<bits/stdc++.h>
using namespace std;
inline static const nullptr_t _=[](){
    ios::sync_with_stdio(0);
    cin.tie(nullptr),cout.tie(nullptr);
    return nullptr;
}();
int n,m,ans;
vector<int> g[10005];
bitset<10005> vis;

void dfs(int i){
    for(int j=0;j<g[i].size();j++){
        if(!vis[g[i][j]]){
            vis[g[i][j]]=1;
            dfs(g[i][j]);
        }
    }
}

int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        g[u].emplace_back(v);
        g[v].emplace_back(u);
    }
    for(int i=1;i<=n;i++){
        if(!vis[i]){
            vis[i]=1;
            dfs(i);
            ans++;
        }
    }
    cout<<ans<<'\n';
    return 0;
}

现在，代码应该能够正确地找到给定图中的连通分量数量。