Wsrtjtyk

Guys I am new to competitive programming ,I am facing a small problem
while giving input
In the question number of vertices are starting from 1 to n
But i write the program considering that nodes are starting from 0

But when i am giving input the test cases by reducing 1 from each vertices for each edge my program is running fine out of the given test cases;

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

Link for the question:

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

But when i am changing what i am changing
graph[(u-1)][(v-1)] = 1;
graph[(v-1)][(u-1)] = 1; while taking input edges
also here alice[(vchild-1)] = (upar-1);
to take the given test case as it is in my program but my answer coming wrong this time I am also reducing 1 from each vertices while taking input edges Why this is happening?

    #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/%dn", win, ver);

            t--;

        }









    }

Your code has several problems:

• The scope of your variables is too wide. You reuse variables without resetting them. You can avoid that by using the closest possible scope when defining variables and by initialising them when you define them. (Reusing old values applies to your parent and visited arrays and to the count.


• When you count Alice's correct guesses, the iterating variable of the inner loop is j, but yu test alice[i] and parent[i].


• When you simplify the fraction, the if should be a while, otherwise you will miss out on squares and cubes.


• In main, you mix up the number of vertices ver and the variable v a lot.

But why do the outputs differ when you give the zero-indexd variables as input?

As I said above, you use v often when you really want ver. The variable v is used only correctly when you scan the edges and is, of course, different for one-based and zero-based input. Close scpoing is your friend here, too: Make u and v local to the loop where you scan the edges.

(For what it's worth, I don't think the matrix representation of the graph is useful for larger graphs, because the graph is sparse. You may lose a lot of time when scanning through rows of 100,000 entries repeatedly.)