Graph Ordering 题解

问题分析

我们需要找到一个节点排列，使得：

1. 从源节点（第一个节点）到每个节点都有合法路径
2. 从每个节点到汇节点（最后一个节点）都有合法路径

合法路径要求：路径上的每条边 $(a,b)$ 必须满足 $a$ 在排列中位于 $b$ 之前。

核心思路

关键观察：

这个问题等价于找到图的一个双连通分量的线性化，使得：

• 源节点在第一个双连通分量中
• 汇节点在最后一个双连通分量中
• 每个双连通分量内部可以任意排序
• 双连通分量之间形成一条链

算法步骤：

1. 找到所有双连通分量
2. 构建块切割树（block-cut tree）
3. 在块切割树上找到从源到汇的路径
4. 沿着路径输出节点

完整代码实现

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

#define MAXN 100005
#define MAXM 400005

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

Node* graph[MAXN];
Node* bc_tree[MAXN * 2];  // 块切割树，最多2n个节点
int visited[MAXN];
int disc[MAXN], low[MAXN], parent[MAXN];
int stack[MAXN], top = -1;
int comp_id[MAXN], comp_count = 0;
int is_articulation[MAXN];
int n, m;

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

// Tarjan算法找双连通分量
void tarjan(int u, int* time) {
    disc[u] = low[u] = ++(*time);
    int children = 0;
    
    Node* curr = graph[u];
    while (curr != NULL) {
        int v = curr->v;
        if (disc[v] == -1) {
            children++;
            parent[v] = u;
            stack[++top] = v;
            tarjan(v, time);
            
            low[u] = (low[u] < low[v]) ? low[u] : low[v];
            
            // 检查u是否是关节点
            if ((parent[u] == -1 && children > 1) || 
                (parent[u] != -1 && low[v] >= disc[u])) {
                is_articulation[u] = 1;
                
                // 弹出栈直到v，形成一个双连通分量
                comp_count++;
                while (stack[top] != v) {
                    comp_id[stack[top]] = comp_count;
                    top--;
                }
                comp_id[v] = comp_count;
                top--;
            }
        } else if (v != parent[u]) {
            low[u] = (low[u] < disc[v]) ? low[u] : disc[v];
        }
        curr = curr->next;
    }
}

// 构建块切割树
void build_block_cut_tree() {
    memset(disc, -1, sizeof(disc));
    memset(low, -1, sizeof(low));
    memset(parent, -1, sizeof(parent));
    memset(is_articulation, 0, sizeof(is_articulation));
    memset(comp_id, 0, sizeof(comp_id));
    
    int time = 0;
    comp_count = 0;
    top = -1;
    
    // 对每个未访问的节点运行Tarjan
    for (int i = 1; i <= n; i++) {
        if (disc[i] == -1) {
            stack[++top] = i;
            tarjan(i, &time);
            
            // 处理根节点的剩余分量
            if (top >= 0) {
                comp_count++;
                while (top >= 0) {
                    comp_id[stack[top]] = comp_count;
                    top--;
                }
            }
        }
    }
    
    // 构建块切割树
    for (int u = 1; u <= n; u++) {
        if (is_articulation[u]) {
            // 关节点连接到它所在的所有分量
            Node* curr = graph[u];
            while (curr != NULL) {
                int v = curr->v;
                if (comp_id[u] != comp_id[v]) {
                    add_edge(bc_tree, u, comp_id[v] + n);
                    add_edge(bc_tree, comp_id[v] + n, u);
                }
                curr = curr->next;
            }
        }
    }
}

// 在块切割树上DFS找路径
int dfs_find_path(int u, int target, int* path, int* path_len, int* visited_bc) {
    if (u == target) {
        path[(*path_len)++] = u;
        return 1;
    }
    
    visited_bc[u] = 1;
    
    Node* curr = bc_tree[u];
    while (curr != NULL) {
        int v = curr->v;
        if (!visited_bc[v]) {
            if (dfs_find_path(v, target, path, path_len, visited_bc)) {
                path[(*path_len)++] = u;
                return 1;
            }
        }
        curr = curr->next;
    }
    
    return 0;
}

// 输出排列
void output_ordering(int source, int sink) {
    int visited_bc[MAXN * 2] = {0};
    int path[MAXN * 2], path_len = 0;
    
    // 在块切割树上找从源到汇的路径
    if (!dfs_find_path(source, sink, path, &path_len, visited_bc)) {
        printf("IMPOSSIBLE\n");
        return;
    }
    
    // 输出路径上的节点
    int result[MAXN], result_len = 0;
    int used[MAXN] = {0};
    
    for (int i = path_len - 1; i >= 0; i--) {
        int node = path[i];
        if (node <= n) {  // 原始图节点
            if (!used[node]) {
                result[result_len++] = node;
                used[node] = 1;
            }
        } else {  // 双连通分量
            int comp = node - n;
            // 输出该分量中所有未使用的节点
            for (int j = 1; j <= n; j++) {
                if (comp_id[j] == comp && !used[j]) {
                    result[result_len++] = j;
                    used[j] = 1;
                }
            }
        }
    }
    
    // 输出结果
    for (int i = 0; i < result_len; i++) {
        printf("%d", result[i]);
        if (i < result_len - 1) printf(" ");
    }
    printf("\n");
}

int main() {
    scanf("%d %d", &n, &m);
    
    // 读取边
    for (int i = 0; i < m; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        add_edge(graph, a, b);
        add_edge(graph, b, a);
    }
    
    // 构建块切割树
    build_block_cut_tree();
    
    // 选择源和汇（这里选择1和n，根据题目可以调整）
    int source = 1, sink = n;
    
    // 输出排列
    output_ordering(source, sink);
    
    // 清理内存
    for (int i = 1; i <= n; i++) {
        Node* curr = graph[i];
        while (curr != NULL) {
            Node* temp = curr;
            curr = curr->next;
            free(temp);
        }
    }
    
    for (int i = 1; i <= n * 2; i++) {
        Node* curr = bc_tree[i];
        while (curr != NULL) {
            Node* temp = curr;
            curr = curr->next;
            free(temp);
        }
    }
    
    return 0;
}

简化版本：基于BFS的启发式方法

对于某些情况，可以使用更简单的方法：

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

#define MAXN 100005
#define MAXM 400005

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

Node* graph[MAXN];
int visited[MAXN];
int order[MAXN], order_len = 0;
int in_degree[MAXN], out_degree[MAXN];

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

// 检查从source出发的BFS
int bfs_from_source(int source, int n) {
    memset(visited, 0, sizeof(visited));
    int queue[MAXN], front = 0, rear = 0;
    
    queue[rear++] = source;
    visited[source] = 1;
    
    while (front < rear) {
        int u = queue[front++];
        order[order_len++] = u;
        
        Node* curr = graph[u];
        while (curr != NULL) {
            int v = curr->v;
            if (!visited[v]) {
                visited[v] = 1;
                queue[rear++] = v;
            }
            curr = curr->next;
        }
    }
    
    return (order_len == n);
}

// 检查反向BFS（从sink出发在反图中）
int reverse_bfs_from_sink(int sink, int n) {
    // 构建反图
    Node* reverse_graph[MAXN] = {NULL};
    for (int u = 1; u <= n; u++) {
        Node* curr = graph[u];
        while (curr != NULL) {
            int v = curr->v;
            add_edge(reverse_graph, v, u);
            curr = curr->next;
        }
    }
    
    memset(visited, 0, sizeof(visited));
    int queue[MAXN], front = 0, rear = 0;
    int reverse_order[MAXN], reverse_len = 0;
    
    queue[rear++] = sink;
    visited[sink] = 1;
    
    while (front < rear) {
        int u = queue[front++];
        reverse_order[reverse_len++] = u;
        
        Node* curr = reverse_graph[u];
        while (curr != NULL) {
            int v = curr->v;
            if (!visited[v]) {
                visited[v] = 1;
                queue[rear++] = v;
            }
            curr = curr->next;
        }
    }
    
    // 清理反图内存
    for (int i = 1; i <= n; i++) {
        Node* curr = reverse_graph[i];
        while (curr != NULL) {
            Node* temp = curr;
            curr = curr->next;
            free(temp);
        }
    }
    
    return (reverse_len == n);
}

// 尝试找到合法排列
int find_valid_ordering(int n) {
    // 尝试不同的源和汇组合
    for (int source = 1; source <= n; source++) {
        for (int sink = 1; sink <= n; sink++) {
            if (source == sink) continue;
            
            order_len = 0;
            if (bfs_from_source(source, n) && reverse_bfs_from_sink(sink, n)) {
                // 检查是否满足所有边的方向约束
                int valid = 1;
                for (int u = 1; u <= n && valid; u++) {
                    Node* curr = graph[u];
                    while (curr != NULL && valid) {
                        int v = curr->v;
                        // 找到u和v在order中的位置
                        int pos_u = -1, pos_v = -1;
                        for (int i = 0; i < n; i++) {
                            if (order[i] == u) pos_u = i;
                            if (order[i] == v) pos_v = i;
                        }
                        if (pos_u > pos_v) {
                            valid = 0;
                        }
                        curr = curr->next;
                    }
                }
                
                if (valid) {
                    return 1;
                }
            }
        }
    }
    return 0;
}

int main() {
    scanf("%d %d", &n, &m);
    
    // 读取边
    for (int i = 0; i < m; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        add_edge(a, b);
        add_edge(b, a);
    }
    
    if (find_valid_ordering(n)) {
        for (int i = 0; i < n; i++) {
            printf("%d", order[i]);
            if (i < n - 1) printf(" ");
        }
        printf("\n");
    } else {
        printf("IMPOSSIBLE\n");
    }
    
    // 清理内存
    for (int i = 1; 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 100005

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

Node* graph[MAXN];
int visited[MAXN];
int order[MAXN];
int pos[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
int topological_bfs(int n) {
    int queue[MAXN], front = 0, rear = 0;
    int in_degree[MAXN] = {0};
    
    // 计算"伪入度" - 需要出现在当前节点之前的邻居数量
    for (int u = 1; u <= n; u++) {
        Node* curr = graph[u];
        while (curr != NULL) {
            in_degree[curr->v]++;
            curr = curr->next;
        }
    }
    
    // 找到可能的起点（入度为0或较小）
    for (int u = 1; u <= n; u++) {
        if (in_degree[u] == 0) {
            queue[rear++] = u;
            visited[u] = 1;
        }
    }
    
    // 如果没有入度为0的节点，选择任意起点
    if (rear == 0) {
        queue[rear++] = 1;
        visited[1] = 1;
    }
    
    int order_len = 0;
    while (front < rear) {
        int u = queue[front++];
        order[order_len++] = u;
        pos[u] = order_len - 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 order_len;
}

// 验证排列是否合法
int validate_ordering(int n) {
    // 检查每条边是否满足方向约束
    for (int u = 1; u <= n; u++) {
        Node* curr = graph[u];
        while (curr != NULL) {
            int v = curr->v;
            if (pos[u] > pos[v]) {
                return 0;
            }
            curr = curr->next;
        }
    }
    return 1;
}

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    
    // 读取边
    for (int i = 0; i < m; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        add_edge(a, b);
        add_edge(b, a);
    }
    
    // 尝试生成排列
    int order_len = topological_bfs(n);
    
    if (order_len == n && validate_ordering(n)) {
        for (int i = 0; i < n; i++) {
            printf("%d", order[i]);
            if (i < n - 1) printf(" ");
        }
        printf("\n");
    } else {
        printf("IMPOSSIBLE\n");
    }
    
    // 清理内存
    for (int i = 1; i <= n; i++) {
        Node* curr = graph[i];
        while (curr != NULL) {
            Node* temp = curr;
            curr = curr->next;
            free(temp);
        }
    }
    
    return 0;
}

算法核心思路

1. 图分解：将图分解为双连通分量
2. 路径构造：在块切割树上找到源到汇的路径
3. 节点排序：沿着路径输出节点，同一分量内任意排序
4. 验证检查：确保所有边满足方向约束

复杂度分析

• 时间复杂度：$O(n + m)$
• 空间复杂度：$O(n + m)$

这些解决方案提供了从简单到复杂的多种方法，可以根据具体问题规模选择合适的方法。