【ACM】POJ 1611 The Suspects-白红宇

【ACM】POJ 1611 The Suspects

阅读量：362 次

发布时间：2019-03-04

本文共 1489 字，大约阅读时间需要 4 分钟。

为了找出所有的嫌疑人，我们可以使用并查集（Union-Find）数据结构来高效地解决这个问题。具体来说，每个学生都被看作一个集合，当一个小组包含嫌疑人时，该小组的所有成员都会被合并到一个大集合中。这样，所有在大集合中的学生就是嫌疑人。

步骤解释：

初始化并查集，每个学生是一个独立的集合。

标记学生0为嫌疑人。

对于每个小组，检查该小组的成员是否至少有一个嫌疑人。如果有，则将该小组的所有成员合并到一个集合中，并将该集合与嫌疑人集合合并。

最后，统计所有在嫌疑人集合中的学生数量。

代码实现：

#include 
   
    
#include 
    
     
using namespace std;
int find(int a, int parent[]);
void union(int a, int b, int parent[], int rank[]);
void main() {
    int n = 0, m = 0;
    bool hasStudent = false;
    vector
     
       parent(n), rank(n);
    for(int i=0; i
      
       > n_line >> m_line)) break;
        hasStudent = true;
        n = n_line;
        m = m_line;
        if(n == 0) break;
        parent.resize(n);
        rank.resize(n);
        for(int i=0; i

groups;

for(int i=0; i

> *p && !isspace(*p) ) { *p = 0; groups.push_back(*p); } k = groups.size(); if(k == 0) continue; groups.erase(unique(groups.begin() + 1, groups.end(), [](int a, int b) { return a > b; }), groups.end()); for(int student : groups) { if(student >= n) continue; if(student == 0) { // Mark all in this group as suspicious // Find the root of student 0 int root = find(0, parent); for(int s : groups) { if(! (s == 0)) { int root_s = find(s, parent); if(root_s != root) { union(root, root_s, parent, rank); } } } break; } } } if(n == 0 || m == 0) break; } if(hasStudent) { int root = find(0, parent); int count = 0; for(int i=0; i

这个代码使用并查集来高效地处理每个小组，确保所有的嫌疑人都被正确标记。最终统计并输出嫌疑人的数量。

转载地址：http://inzg.baihongyu.com/

你可能感兴趣的文章

Objective-C实现广度优先搜寻树遍历算法（附完整源码）