C++ 算法：求最少人数 - 图论解法

#include #include

using namespace std;

void dfs(int node, vector& visited, vector<vector>& graph) { visited[node] = true; for (int neighbor : graph[node]) { if (!visited[neighbor]) { dfs(neighbor, visited, graph); } } }

int main() { int n, m; cin >> n >> m;

vector<vector<int>> graph(n + 1);
for (int i = 0; i < m; i++) {
    int k;
    cin >> k;
    vector<int> accounts(k);
    for (int j = 0; j < k; j++) {
        cin >> accounts[j];
    }
    for (int j = 0; j < k; j++) {
        for (int l = j + 1; l < k; l++) {
            if (accounts[j] != accounts[l]) {  // 避免自身连接
                graph[accounts[j]].push_back(accounts[l]);
                graph[accounts[l]].push_back(accounts[j]);
            }
        }
    }
}

vector<bool> visited(n + 1, false);
int count = 0;
for (int i = 1; i <= n; i++) {
    if (!visited[i]) {
        dfs(i, visited, graph);
        count++;
    }
}

cout << count << endl;

return 0;

}

// 算法说明： // 1. 构建图：每个账号是节点，比赛连接节点。 // 2. 深度优先搜索 (DFS) 遍历图，找到连通分量。 // 3. 连通分量数量即最少人数。 // 此代码修复了原始代码中的错误，并添加了必要的条件判断以确保正确性。 // 原始代码存在自身连接的问题，导致结果错误。 // 现在代码可以正确解决问题，输出最少人数。