показывает разные выходные данные для одного и того же ввода (почти)

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-история-из-а-дерево-английски? AWSAccessKeyId = AKIAJ4WZFDFQTZRGO3QA & Истекает = 1542565481 & Signature = WoegY4gKUz0OUDEQ3n2UT80FUc0% 3D и ответ-контента диспозиция = рядный% 3B% 20filename% 3Dthe-story-of-a-tree-English.pdf & response-content-type = application% 2Fpdf

Но когда я меняю то, что я меняю graph[(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.
• Когда вы считаете правильные догадки Алисы, итерационная переменная внутреннего цикла равна j, но вы проверяете alice[i] и parent[i].
• Когда вы упрощаете дробь, if должно быть while, иначе вы пропустите квадраты и кубы.
• В main вы смешиваете количество вершин ver и переменную v.

Но почему выходы отличаются, когда вы задаете переменные с нулевым индексом в качестве входных данных?

Как я уже говорил выше, вы часто используете v, когда действительно хотите ver. Переменная v используется только правильно, когда вы сканируете края, и, разумеется, она отличается для ввода на основе одного и нуля. Твой друг здесь тоже близок: сделай u и v локальными для петли, где ты сканируешь края.

(Я не думаю, что матричное представление графика полезно для больших графов, потому что граф разрежен. Вы можете потерять много времени при многократном сканировании строк по 100 000 записей.)