c - 显示相同输入的不同输出(几乎)

Question

伙计们，我是竞争性编程的新手，我遇到了一个小问题在提供输入的同时在问题中，顶点数从 1 到 n但是我编写程序时考虑到节点是从 0 开始的

但是当我通过从每个边的每个顶点减少 1 来输入测试用例时，我的程序在给定的测试用例中运行良好；

given test case;
1(checking for first one only otherwise 2 was given)
4
1 2
1 3
3 4
2 2
1 2
3 4

my test case(after reducing 1 from edges):
1
4
0 1
0 2
2 3
2 2
0 1
2 3

问题链接:

https://hackerrank-challenge-pdfs.s3.amazonaws.com/29036-the-story-of-a-tree-English?AWSAccessKeyId=AKIAJ4WZFDFQTZRGO3QA&Expires=1542565481&Signature=WoegY4gKUz0OUDEQ3n2UT80FUc0%3D&response-content-disposition=inline%3B%20filename%3Dthe-story-of-a-tree-English.pdf&response-content-type=application%2Fpdf

但是当我改变我正在改变的东西时 图[(u-1)][(v-1)] = 1; graph[(v-1)][(u-1)] = 1; 同时取输入边也在这里 alice[(vchild-1)] = (upar-1);在我的程序中采用给定的测试用例，但这次我的答案是错误的我也在获取输入边时从每个顶点减少 1 为什么会发生这种情况？

    #pragma warning(disable:4996)
    #include<stdio.h>
    #include<stdlib.h>
    int visited[1000],parent[100],alice[100];
    struct queue {
        int rear;
        int front;
        int capacity;
        int* array;
    };

    struct queue* createqueue(int capacity) {
        struct queue* Q = (struct queue*)malloc(sizeof(struct queue));
        Q->capacity = capacity;
        Q->front = -1;
        Q->rear = -1;
        Q->array = (int*)malloc(sizeof(int)*capacity);
        return Q;
    }
    int isempty(struct queue* Q) {
        return(Q->front == -1 && Q->rear == -1);

    }
    int isfull(struct queue* Q) {
        return((Q->rear + 1) % Q->capacity == Q->front);

    }
    void push(struct queue* Q, int data) {
        if (isfull(Q))
            return;
        else if (isempty(Q))
        {
            Q->rear = 0;
            Q->front = 0;
            Q->array[Q->rear] = data;
        }
        else {
            Q->rear = ((Q->rear + 1) % Q->capacity);
            Q->array[Q->rear] = data;
        }
    }
    int pop(struct queue* Q) {
        if (isempty(Q))
            return -1;
        else if (Q->rear == Q->front) {
            int temp = Q->rear;
            Q->rear = -1;
            Q->front = -1;
            return(Q->array[temp]);
        }
        else {
            int temp = Q->front;
            Q->front = ((Q->front + 1) % Q->capacity);
            return Q->array[temp];

        }
    }
    void bfs(int** graph ,int ver,int s) {
        struct queue* Q=createqueue(100);
        push(Q, s);
        visited[s] = 1;
        int v, w;
        while (!isempty(Q)) {
            v = pop(Q);
            for (int j = 0; j < ver; j++) {
                if (visited[j] == 0 && graph[v][j] == 1)
                {
                    parent[j] = v;
                    push(Q, j);
                    visited[j] = 1;
                }
            }
        }
    }
    int main() {
        int t;
        scanf("%d", &t);
        while (t) {
            int** graph;
            int i, ver, u, v;
            scanf("%d", &ver);
            graph = (int**)malloc(sizeof(int*)*ver);
            for (i = 0; i < ver; i++)
                graph[i] = (int*)malloc(sizeof(int)*ver);
            for (int i = 0; i < ver; i++) {
                for (int j = 0; j < ver; j++) {
                    graph[i][j] = 0;
                }
            }
            //  printf("%d", graph[1][1]);
            for (int j = 0; j < ver - 1; j++) {
                scanf("%d %d", &u, &v);
                graph[u-1][v-1] = 1;
                graph[v-1][u-1] = 1;
            }
            int g, k;
            scanf("%d %d", &g, &k);
            int count = 0, win = 0;
            int vchild, upar;
            for (int i = 0; i < ver; i++)
                alice[i] = -1;
            for (int i = 0; i < g; i++) {
                scanf("%d %d", &upar, &vchild);
                alice[vchild-1] = upar-1;
            }
            for (int i = 0; i < v; i++) {
                bfs(graph, v, i);
                for (int j = 0; j < v; j++) {
                    if (alice[i] != -1 && alice[i] == parent[i])
                        count++;
                }
                if (count >= k)
                    win++;
            }
            for (int i = 2; i <= win && i <= ver; i++) {
                if (win%i == 0 && ver%i == 0) {
                    win = win / i;
                    ver = ver / i;
                }
            }
            printf("%d/%d\n", win, ver);
            t--;
        }




    }

Answer 1

您的代码有几个问题:

• 您的变量范围太广。您重用变量而不重置它们。您可以通过在定义变量时使用尽可能接近的范围并在定义它们时初始化它们来避免这种情况。 (重用旧值适用于您的 parent 和 visited 数组以及 count。
• 当你计算 Alice 的正确猜测时，内循环的迭代变量是 j，但是你测试 alice[i] 和 parent[i]。
• 当你简化分数时，if 应该是一个while，否则你会错过正方形和立方体。
• 在 main 中，您经常混淆顶点数 ver 和变量 v。

但是，当您将零索引变量作为输入时，为什么输出会有所不同？

正如我上面所说的，当您确实需要 ver 时，您经常使用 v。变量 v 只有在扫描边缘时才能正确使用，当然，对于基于 1 和基于 0 的输入是不同的。关闭 scpoing 也是您的 friend :将 u 和 v 设置为扫描边缘的循环的本地。

(就其值(value)而言，我认为图的矩阵表示对于较大的图没有用，因为图是稀疏的。重复扫描 100,000 个条目的行可能会浪费很多时间。)