构建有向无环图（DAG）技术求助：无法跳过形成环的边对

Hey there, let's walk through the issues in your code and fix them step by step. I see you're trying to build a DAG by adding edges one by one and skipping any that create a cycle—great approach, but there are a few key bugs throwing things off. Let's break down the problems and implement a working solution.

Key Issues in Your Current Code #

Let's start with the most obvious blockers:

1. Early return in the DAG function
   Your loop over pairs has a return; statement inside it, which means the function exits after processing the first edge pair. You'll never get to check or add the rest of the edges!

2. Uninitialized state arrays for cycle detection
   Every time you call cyclicGraph, the visited and onStack arrays are filled with garbage values (since they're local stack variables). This makes your DFS-based cycle check completely unreliable—you can't trust the results.

3. Mismatched array references
   In hasCycle, you're checking locked[x][i], but your code uses matrix to store the current edges. This means your DFS isn't actually traversing the graph you're building.

4. Inefficient cycle detection logic
   Checking the entire graph for cycles after every edge addition is overkill. When you add an edge from -> to, the only way this creates a cycle is if there's already a path from to back to from. We can optimize the check to only verify this specific path, which is faster and avoids false positives.

Corrected Code Implementation #

Here's the fixed version with explanations:

First, let's clean up the global variables (and define missing ones like pair_count and matrix):

#include <stdbool.h>
#include <stdio.h>

#define MAX 9 // Define max players explicitly (since you said <=9)
int pair_count = 0; // Track number of valid edge pairs
bool matrix[MAX][MAX] = {false}; // Initialize adjacency matrix to false

typedef struct {
    int winner;
    int loser;
} pair; 
pair pairs[MAX * (MAX - 1) / 2]; // Store all valid edge pairs

Next, let's rewrite the cycle detection to check if a path exists from target to start (this tells us if adding start->target creates a cycle):

// Helper to check if there's a path from 'src' to 'dest' using DFS
bool hasPath(int src, int dest, bool visited[]) {
    if (src == dest) {
        return true; // Found a path
    }
    visited[src] = true;
    for (int i = 0; i < MAX; i++) {
        if (matrix[src][i] && !visited[i]) {
            if (hasPath(i, dest, visited)) {
                return true;
            }
        }
    }
    return false;
}

Now fix the DAG function to properly process all edges and skip cycle-causing ones:

void buildDAG(void) {
    for (int i = 0; i < pair_count; i++) {
        int from = pairs[i].winner;
        int to = pairs[i].loser;

        // First, check if adding from->to would create a cycle
        bool visited[MAX] = {false}; // Initialize visited array to false
        if (hasPath(to, from, visited)) {
            // Path exists from 'to' to 'from'—adding this edge creates a cycle, skip it
            continue;
        }

        // No cycle, add the edge to the matrix
        matrix[from][to] = true;
    }
}

Finally, update your main function to call the corrected buildDAG (and make sure you populate pair_count and pairs correctly from input):

int main(void) {
    // ... Your input handling code here to populate MAX, results, pairs, and pair_count ...
    // Remember to sort pairs by winner in descending order as you mentioned

    buildDAG();

    // Optional: Print the final DAG matrix to verify
    printf("Final DAG Adjacency Matrix:\n");
    for (int i = 0; i < MAX; i++) {
        for (int j = 0; j < MAX; j++) {
            printf("%d ", matrix[i][j] ? 1 : 0);
        }
        printf("\n");
    }

    return 0;
}

Additional Notes #

• Global variables: I used global variables here to match your original code, but in larger C projects, it's better to pass these as parameters to functions to avoid scope issues.
• Input handling: Make sure you correctly populate pair_count when adding valid edge pairs (only when results[A][B] != results[B][A]).
• Sorting pairs: Don't forget to sort the pairs array by winner in descending order before calling buildDAG—your original comment mentioned this step, which is important for your use case.

内容的提问来源于stack exchange，提问作者zyniger