Island Alliances 题解

问题分析

这是一个动态合并集合的问题，但带有约束条件：

• 初始每个岛屿独立
• 有 $m$ 对不信任关系
• 每次合并两个集合时，检查这两个集合中是否包含不信任的岛屿对
• 如果包含则拒绝合并，否则批准并合并

核心思路

使用并查集维护岛屿的合并关系，但对于不信任关系的检查需要高效方法。

关键观察：

• 如果两个集合要合并，需要检查一个集合中的每个岛屿与另一个集合中的每个岛屿是否存在不信任关系
• 朴素方法复杂度太高，需要优化

优化策略：按秩合并 + 小集合检查

对于每个集合，维护其不信任的岛屿集合。合并时，检查较小的集合中的每个岛屿是否与较大集合中的任何岛屿有不信任关系。

数据结构设计

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAXN 100005

typedef struct Node {
    int val;
    struct Node* next;
} Node;

// 并查集
int parent[MAXN];
int size[MAXN];

// 邻接表存储不信任关系
Node* distrust[MAXN];

完整代码实现

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAXN 100005

typedef struct Node {
    int val;
    struct Node* next;
} Node;

// 并查集
int parent[MAXN];
int size[MAXN];

// 邻接表存储不信任关系
Node* distrust[MAXN];

// 并查集查找
int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]);
    }
    return parent[x];
}

// 添加不信任关系
void add_distrust(int u, int v) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->val = v;
    node->next = distrust[u];
    distrust[u] = node;
}

// 检查两个集合是否可以合并
int can_merge(int set_a, int set_b) {
    // 总是让set_a是较小的集合
    if (size[set_a] > size[set_b]) {
        int temp = set_a;
        set_a = set_b;
        set_b = temp;
    }
    
    // 检查set_a中的每个岛屿是否与set_b中的任何岛屿有不信任关系
    for (int i = 1; i < MAXN; i++) {
        if (find(i) == set_a) {
            // 检查岛屿i的所有不信任关系
            Node* curr = distrust[i];
            while (curr != NULL) {
                if (find(curr->val) == set_b) {
                    return 0; // 发现不信任关系，不能合并
                }
                curr = curr->next;
            }
        }
    }
    
    return 1; // 可以合并
}

// 合并两个集合
void merge_sets(int a, int b) {
    int root_a = find(a);
    int root_b = find(b);
    
    if (root_a == root_b) return;
    
    // 按秩合并
    if (size[root_a] < size[root_b]) {
        parent[root_a] = root_b;
        size[root_b] += size[root_a];
    } else {
        parent[root_b] = root_a;
        size[root_a] += size[root_b];
    }
}

int main() {
    int n, m, q;
    scanf("%d %d %d", &n, &m, &q);
    
    // 初始化并查集
    for (int i = 1; i <= n; i++) {
        parent[i] = i;
        size[i] = 1;
        distrust[i] = NULL;
    }
    
    // 读取不信任关系
    for (int i = 0; i < m; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        add_distrust(u, v);
        add_distrust(v, u); // 不信任关系是双向的
    }
    
    // 处理提案
    for (int i = 0; i < q; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        
        int set_a = find(a);
        int set_b = find(b);
        
        if (set_a == set_b) {
            printf("APPROVE\n");
            continue;
        }
        
        if (can_merge(set_a, set_b)) {
            printf("APPROVE\n");
            merge_sets(a, b);
        } else {
            printf("REFUSE\n");
        }
    }
    
    // 释放内存
    for (int i = 1; i <= n; i++) {
        Node* curr = distrust[i];
        while (curr != NULL) {
            Node* temp = curr;
            curr = curr->next;
            free(temp);
        }
    }
    
    return 0;
}

算法优化版本

上面的基础版本对于大数据可能较慢，下面是优化版本：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAXN 100005

typedef struct Node {
    int val;
    struct Node* next;
} Node;

int parent[MAXN];
int size[MAXN];
Node* distrust[MAXN];
int visited[MAXN];
int temp_visited[MAXN];

int find(int x) {
    return parent[x] == x ? x : (parent[x] = find(parent[x]));
}

void add_distrust(int u, int v) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->val = v;
    node->next = distrust[u];
    distrust[u] = node;
}

// 优化的检查函数 - 使用临时标记数组
int can_merge_optimized(int set_a, int set_b) {
    // 让set_a是较小的集合
    if (size[set_a] > size[set_b]) {
        int temp = set_a;
        set_a = set_b;
        set_b = temp;
    }
    
    static int timestamp = 0;
    timestamp++;
    
    // 标记set_b中的所有岛屿
    for (int i = 1; i < MAXN; i++) {
        if (find(i) == set_b) {
            temp_visited[i] = timestamp;
        }
    }
    
    // 检查set_a中的岛屿是否与set_b中的岛屿有不信任关系
    for (int i = 1; i < MAXN; i++) {
        if (find(i) == set_a) {
            Node* curr = distrust[i];
            while (curr != NULL) {
                if (temp_visited[curr->val] == timestamp) {
                    return 0;
                }
                curr = curr->next;
            }
        }
    }
    
    return 1;
}

void merge_sets(int a, int b) {
    int root_a = find(a);
    int root_b = find(b);
    
    if (root_a == root_b) return;
    
    if (size[root_a] < size[root_b]) {
        parent[root_a] = root_b;
        size[root_b] += size[root_a];
    } else {
        parent[root_b] = root_a;
        size[root_a] += size[root_b];
    }
}

int main() {
    int n, m, q;
    scanf("%d %d %d", &n, &m, &q);
    
    // 初始化
    for (int i = 1; i <= n; i++) {
        parent[i] = i;
        size[i] = 1;
        distrust[i] = NULL;
        temp_visited[i] = 0;
    }
    
    // 读取不信任关系
    for (int i = 0; i < m; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        add_distrust(u, v);
        add_distrust(v, u);
    }
    
    // 处理提案
    for (int i = 0; i < q; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        
        int set_a = find(a);
        int set_b = find(b);
        
        if (set_a == set_b) {
            printf("APPROVE\n");
            continue;
        }
        
        if (can_merge_optimized(set_a, set_b)) {
            printf("APPROVE\n");
            merge_sets(a, b);
        } else {
            printf("REFUSE\n");
        }
    }
    
    // 清理内存
    for (int i = 1; i <= n; i++) {
        Node* curr = distrust[i];
        while (curr != NULL) {
            Node* temp = curr;
            curr = curr->next;
            free(temp);
        }
    }
    
    return 0;
}

算法核心步骤详解

1. 初始化阶段

for (int i = 1; i <= n; i++) {
    parent[i] = i;      // 每个岛屿初始独立
    size[i] = 1;        // 每个集合大小为1
    distrust[i] = NULL; // 初始化不信任列表
}

2. 不信任关系存储

void add_distrust(int u, int v) {
    // 使用邻接表存储，u不信任v
    Node* node = (Node*)malloc(sizeof(Node));
    node->val = v;
    node->next = distrust[u];
    distrust[u] = node;
}

3. 合并检查优化

int can_merge_optimized(int set_a, int set_b) {
    // 总是检查较小的集合，降低复杂度
    if (size[set_a] > size[set_b]) {
        swap(set_a, set_b);
    }
    
    // 使用时间戳标记法快速检查
    timestamp++;
    // 标记较大集合中的所有岛屿
    // 检查较小集合中的岛屿是否与标记的岛屿有不信任关系
}

复杂度分析

• 空间复杂度: $O(n + m)$
• 时间复杂度:
  • 并查集操作: $O(\alpha(n))$ 每次
  • 合并检查: 平均 $O(\frac{n}{k} \cdot d)$，其中 $d$ 是平均度数
  • 总复杂度: 约 $O(n \log n + m + q \cdot \frac{n}{k} \cdot d)$

样例验证

样例1

输入: 3 1 2
不信任: 1-2
提案1: 2-1 → REFUSE (1和2不信任)
提案2: 1-3 → APPROVE (无不信任冲突)

样例2

输入: 8 3 7
不信任: 1-2, 2-3, 3-4
提案处理按顺序进行，动态维护集合关系

注意事项

1. 内存管理: 使用邻接表需要手动释放内存
2. 性能优化: 对于大数据集，检查较小集合可以显著提高性能
3. 正确性: 不信任关系是双向的，需要存储两个方向
4. 边界情况: 处理岛屿编号从1开始的情况

这个C语言实现使用了并查集和邻接表来高效解决岛屿联盟问题，通过优化检查策略来处理大规模数据。