• 图中的支配关系

  • 定义一个带权有向图的数据结构如下：

    
    
    typedef struct GraphStruct{
        int   vertex_num;
        int   edge_num;
        int **edges;
    }GraphStruct;
    typedef struct GraphStruct *Graph;
    typedef unsigned int Vertex;
    
    typedef struct {
        Vertex v;
      Vertex w;
        int    weight;
    } Edge;

  ---

  其中 edges 指向图的邻接矩阵，矩阵元素为对应边上的权重(权重为自然数)。
  定义图中0结点为入口结点；
  定义dom关系为：如果从图的入口结点（即0结点）到结点 n 的每条路径都经过结点 d ，则称结点 d 支配(dominate) n ，记为 d dom n。
  根据该定义，每个结点支配它自己，且入口结点（即0结点）支配包括它自己在内的所有结点。

  请使用上述数据结构，从标准输入读入一个图(该图为联通图)，请找出除入口结点外所有结点间的支配关系，并按下面示例样式输出：

  输入数据示例如下：

  
    
  5,6
  0,1,95
  0,2,41
  1,3,99
  1,4,67
  2,4,95
  3,4,99

  ---

  其中第1行分别为图中结点的个数 5、图中边的个数 6；之后的6行分别是各边的信息，以第2行为例，其表示结点0到1之间有权重为95的有向边，方向为0至1。根据支配关系的定义，该图的支配关系有：

  
    
  0 dom 0
  0 dom 1
  0 dom 2
  0 dom 3
  0 dom 4
  1 dom 1
  1 dom 3
  2 dom 2
  3 dom 3
  4 dom 4

  ---

  因0结点支配所有结点，所以不输出该信息；将其它支配关系按结点编号从小到大的顺序输出如下：

   
  
  (1#1)(1#3)(2#2)(3#3)(4#4)

  其中每一对括号表示一个支配关系，# 表示　dom

​ 以下是本人的题解

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

typedef struct GraphStruct {
    int vertex_num;
    int edge_num;
    int **edges;
} GraphStruct;

typedef struct GraphStruct *Graph;
typedef unsigned int Vertex;

Graph create_graph(int vertex_num, int edge_num) {
    Graph g = (Graph)malloc(sizeof(GraphStruct));
    g->vertex_num = vertex_num;
    g->edge_num = edge_num;
    g->edges = (int **)malloc(vertex_num * sizeof(int *));
    for (int i = 0; i < vertex_num; i++) {
        g->edges[i] = (int *)calloc(vertex_num, sizeof(int));
    }
    return g;
}

void dfspro(Graph g, Vertex v, bool visitedpro[], int ignore) {
    visitedpro[v] = true;
    for (int w = 0; w < g->vertex_num; w++) {
        if (w != ignore && g->edges[v][w] != 0 && !visitedpro[w]) {
            dfspro(g, w, visitedpro, ignore);
        }
    }
}

void dfs(Graph g, Vertex v, bool visited[]) {
    visited[v] = true;
    for (int i = 0; i < g->vertex_num; i++) {
        if (g->edges[v][i] != 0 && !visited[i]) {
            dfs(g, i, visited);
        }
    }
}


void compute_dominators(Graph g) {
    printf("(");
    bool first = true;

    for (int d = 1; d < g->vertex_num; d++) {
        bool *visitedpro = (bool *)calloc(g->vertex_num, sizeof(bool));
        dfspro(g, 0, visitedpro, d);
        bool *visited = (bool *)calloc(g->vertex_num, sizeof(bool));
        dfs(g, 0, visited);
        for (int n = 0; n < g->vertex_num; n++) {
            if (visited[n] ^ visitedpro[n]) {
                if (!first) {
                    printf(")(");
                }
                printf("%d#%d", d, n);
                first = false;
            }
        }
    }

    printf(")\n");
}

int main() {
    int vertex_num, edge_num;
    scanf("%d,%d", &vertex_num, &edge_num);
    if (vertex_num <= 0 || edge_num <= 0) return 0;
    
    Graph g = create_graph(vertex_num, edge_num);

    for (int i = 0; i < edge_num; i++) {
        Vertex v, w;
        int weight;
        scanf("%u,%u,%d", &v, &w, &weight);
        g->edges[v][w] = weight;
    }

    compute_dominators(g);

    return 0;
}