The Elk 题解

问题分析

我们需要找到所有不在任何从母鹿位置 $A$ 到小鹿位置 $B$ 的路径上的节点。这里的路径允许节点重复，但不允许边重复。

关键观察：一个节点是安全的当且仅当它不在 $A$ 和 $B$ 所在的同一个连通分量中，或者在该连通分量中但从 $A$ 到 $B$ 的所有路径都不经过该节点。

核心思路

算法步骤：

1. 找到连通分量：使用 BFS/DFS 确定每个节点所属的连通分量
2. 检查关键节点：在 $A$ 和 $B$ 所在的连通分量中，找到所有在 $A$ 到 $B$ 路径上的节点
3. 识别安全节点：不在同一连通分量或不在关键路径上的节点

关键观察：

• 如果 $A$ 和 $B$ 不在同一连通分量，那么所有节点都是安全的
• 如果在同一连通分量，我们需要找到所有在 $A$ 到 $B$ 简单路径上的节点

完整代码实现

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

#define MAXN 50005
#define MAXM 200005

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

Node* graph[MAXN];
int visited[MAXN];
int component[MAXN];
int comp_count = 0;
int comp_size[MAXN];
int in_path[MAXN];
int safe[MAXN];

// 添加边
void add_edge(int u, int v) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->v = v;
    node->next = graph[u];
    graph[u] = node;
}

// BFS 标记连通分量
void bfs(int start, int comp_id) {
    int queue[MAXN];
    int front = 0, rear = 0;
    
    queue[rear++] = start;
    visited[start] = 1;
    component[start] = comp_id;
    comp_size[comp_id]++;
    
    while (front < rear) {
        int u = queue[front++];
        Node* curr = graph[u];
        while (curr != NULL) {
            int v = curr->v;
            if (!visited[v]) {
                visited[v] = 1;
                component[v] = comp_id;
                comp_size[comp_id]++;
                queue[rear++] = v;
            }
            curr = curr->next;
        }
    }
}

// 检查节点是否在 A 到 B 的路径上
int dfs_check_path(int u, int target, int parent, int* found) {
    if (u == target) {
        *found = 1;
        in_path[u] = 1;
        return 1;
    }
    
    visited[u] = 1;
    int path_found = 0;
    
    Node* curr = graph[u];
    while (curr != NULL) {
        int v = curr->v;
        if (v != parent && !visited[v]) {
            if (dfs_check_path(v, target, u, found)) {
                path_found = 1;
                in_path[u] = 1;
            }
        }
        curr = curr->next;
    }
    
    return path_found;
}

// 找到所有在 A 到 B 路径上的节点
void find_path_nodes(int A, int B, int n) {
    memset(visited, 0, sizeof(visited));
    memset(in_path, 0, sizeof(in_path));
    
    int found = 0;
    dfs_check_path(A, B, -1, &found);
}

int main() {
    int N, M, A, B;
    scanf("%d %d %d %d", &N, &M, &A, &B);
    
    // 初始化图
    for (int i = 0; i < N; i++) {
        graph[i] = NULL;
    }
    
    // 读取边
    for (int i = 0; i < M; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        add_edge(u, v);
        add_edge(v, u);
    }
    
    // 找到所有连通分量
    memset(visited, 0, sizeof(visited));
    memset(component, -1, sizeof(component));
    memset(comp_size, 0, sizeof(comp_size));
    
    for (int i = 0; i < N; i++) {
        if (!visited[i]) {
            bfs(i, comp_count);
            comp_count++;
        }
    }
    
    // 初始化所有节点为安全
    memset(safe, 1, sizeof(safe));
    
    // 如果 A 和 B 在同一连通分量，找到路径上的节点
    if (component[A] == component[B]) {
        find_path_nodes(A, B, N);
        
        // 标记路径上的节点为不安全
        for (int i = 0; i < N; i++) {
            if (in_path[i]) {
                safe[i] = 0;
            }
        }
    }
    
    // 统计安全节点
    int safe_count = 0;
    for (int i = 0; i < N; i++) {
        if (safe[i]) {
            safe_count++;
        }
    }
    
    // 输出结果
    printf("%d\n", safe_count);
    for (int i = 0; i < N; i++) {
        if (safe[i]) {
            printf("%d\n", i);
        }
    }
    
    // 释放内存
    for (int i = 0; i < N; i++) {
        Node* curr = graph[i];
        while (curr != NULL) {
            Node* temp = curr;
            curr = curr->next;
            free(temp);
        }
    }
    
    return 0;
}

优化版本：使用更高效的算法

上面的DFS方法在最坏情况下可能不够高效。下面是使用BFS和父节点记录的方法：

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

#define MAXN 50005
#define MAXM 200005

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

Node* graph[MAXN];
int visited[MAXN];
int parent[MAXN];
int safe[MAXN];
int in_path[MAXN];

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

// BFS 找到一条从 A 到 B 的路径
int bfs_find_path(int A, int B, int n) {
    memset(visited, 0, sizeof(visited));
    memset(parent, -1, sizeof(parent));
    
    int queue[MAXN];
    int front = 0, rear = 0;
    
    queue[rear++] = A;
    visited[A] = 1;
    
    while (front < rear) {
        int u = queue[front++];
        
        if (u == B) {
            return 1; // 找到路径
        }
        
        Node* curr = graph[u];
        while (curr != NULL) {
            int v = curr->v;
            if (!visited[v]) {
                visited[v] = 1;
                parent[v] = u;
                queue[rear++] = v;
            }
            curr = curr->next;
        }
    }
    
    return 0; // 没有路径
}

// 标记路径上的所有节点
void mark_path_nodes(int A, int B) {
    memset(in_path, 0, sizeof(in_path));
    
    // 从 B 回溯到 A
    int current = B;
    while (current != -1) {
        in_path[current] = 1;
        current = parent[current];
    }
}

// 检查连通性
int is_connected(int A, int B, int n) {
    memset(visited, 0, sizeof(visited));
    
    int queue[MAXN];
    int front = 0, rear = 0;
    
    queue[rear++] = A;
    visited[A] = 1;
    
    while (front < rear) {
        int u = queue[front++];
        
        if (u == B) {
            return 1;
        }
        
        Node* curr = graph[u];
        while (curr != NULL) {
            int v = curr->v;
            if (!visited[v]) {
                visited[v] = 1;
                queue[rear++] = v;
            }
            curr = curr->next;
        }
    }
    
    return 0;
}

int main() {
    int N, M, A, B;
    scanf("%d %d %d %d", &N, &M, &A, &B);
    
    // 初始化图
    for (int i = 0; i < N; i++) {
        graph[i] = NULL;
    }
    
    // 读取边
    for (int i = 0; i < M; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        add_edge(u, v);
        add_edge(v, u);
    }
    
    // 初始化所有节点为安全
    memset(safe, 1, sizeof(safe));
    
    // 检查 A 和 B 是否连通
    if (is_connected(A, B, N)) {
        // 找到一条路径并标记路径上的节点
        if (bfs_find_path(A, B, N)) {
            mark_path_nodes(A, B);
            
            // 路径上的节点不安全
            for (int i = 0; i < N; i++) {
                if (in_path[i]) {
                    safe[i] = 0;
                }
            }
        }
    }
    
    // 统计和输出安全节点
    int safe_count = 0;
    for (int i = 0; i < N; i++) {
        if (safe[i]) {
            safe_count++;
        }
    }
    
    printf("%d\n", safe_count);
    for (int i = 0; i < N; i++) {
        if (safe[i]) {
            printf("%d\n", i);
        }
    }
    
    // 清理内存
    for (int i = 0; i < N; i++) {
        Node* curr = graph[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 50005
#define MAXM 200005

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

Node* graph[MAXN];
int visited[MAXN];
int disc[MAXN];    // 发现时间
int low[MAXN];     // 最早可访问的祖先
int parent[MAXN];
int safe[MAXN];
int time_count = 0;

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

// Tarjan算法找割点
void tarjan(int u, int A, int B, int* found_A, int* found_B) {
    visited[u] = 1;
    disc[u] = low[u] = ++time_count;
    int children = 0;
    
    if (u == A) *found_A = 1;
    if (u == B) *found_B = 1;
    
    Node* curr = graph[u];
    while (curr != NULL) {
        int v = curr->v;
        
        if (!visited[v]) {
            children++;
            parent[v] = u;
            int prev_A = *found_A, prev_B = *found_B;
            
            tarjan(v, A, B, found_A, found_B);
            
            low[u] = (low[u] < low[v]) ? low[u] : low[v];
            
            // 如果u是割点，并且A和B在u的不同子树中
            if (parent[u] == -1 && children > 1) {
                if ((prev_A && *found_B && !prev_B) || (prev_B && *found_A && !prev_A)) {
                    safe[u] = 0;
                }
            }
            if (parent[u] != -1 && low[v] >= disc[u]) {
                if ((prev_A && *found_B && !prev_B) || (prev_B && *found_A && !prev_A)) {
                    safe[u] = 0;
                }
            }
        } else if (v != parent[u]) {
            low[u] = (low[u] < disc[v]) ? low[u] : disc[v];
        }
        
        curr = curr->next;
    }
}

// BFS检查连通性
int bfs_connected(int start, int target, int n) {
    if (start == target) return 1;
    
    memset(visited, 0, sizeof(visited));
    int queue[MAXN];
    int front = 0, rear = 0;
    
    queue[rear++] = start;
    visited[start] = 1;
    
    while (front < rear) {
        int u = queue[front++];
        
        Node* curr = graph[u];
        while (curr != NULL) {
            int v = curr->v;
            if (v == target) return 1;
            if (!visited[v]) {
                visited[v] = 1;
                queue[rear++] = v;
            }
            curr = curr->next;
        }
    }
    
    return 0;
}

int main() {
    int N, M, A, B;
    scanf("%d %d %d %d", &N, &M, &A, &B);
    
    // 初始化
    for (int i = 0; i < N; i++) {
        graph[i] = NULL;
        safe[i] = 1; // 初始所有节点安全
    }
    
    // 读取边
    for (int i = 0; i < M; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        add_edge(u, v);
        add_edge(v, u);
    }
    
    // 如果A和B不连通，所有节点都安全
    if (!bfs_connected(A, B, N)) {
        printf("%d\n", N);
        for (int i = 0; i < N; i++) {
            printf("%d\n", i);
        }
        return 0;
    }
    
    // 使用Tarjan算法分析图
    memset(visited, 0, sizeof(visited));
    memset(parent, -1, sizeof(parent));
    time_count = 0;
    
    int found_A = 0, found_B = 0;
    for (int i = 0; i < N; i++) {
        if (!visited[i]) {
            tarjan(i, A, B, &found_A, &found_B);
        }
    }
    
    // A和B本身总是不安全的
    safe[A] = safe[B] = 0;
    
    // 统计安全节点
    int safe_count = 0;
    for (int i = 0; i < N; i++) {
        if (safe[i]) safe_count++;
    }
    
    printf("%d\n", safe_count);
    for (int i = 0; i < N; i++) {
        if (safe[i]) printf("%d\n", i);
    }
    
    // 清理内存
    for (int i = 0; i < N; i++) {
        Node* curr = graph[i];
        while (curr != NULL) {
            Node* temp = curr;
            curr = curr->next;
            free(temp);
        }
    }
    
    return 0;
}

算法核心思路

1. 连通性检查：如果A和B不在同一连通分量，所有节点都安全
2. 路径分析：如果连通，使用图算法找到所有在A到B路径上的节点
3. 安全节点：不在这些路径上的节点就是安全节点

复杂度分析

• 时间复杂度：$O(N + M)$
• 空间复杂度：$O(N + M)$

这个解决方案能够高效处理最大数据规模，正确识别所有安全节点。