I'm trying to write havel-hakimi theorem in C. But I have a problem with the while loop. The program doesn't sort array again in the while loop and that's why output prints the wrong answer. Could show me what's my fault please?

# include <stdio.h>
int main(){
    int j,i,vertex_number,temp1,temp2,a=0,b=0;
    printf("Vertex Number:");
    scanf("%d",&vertex_number);
    int graph[vertex_number];
    for(i=0;i<vertex_number;i  ){
        scanf("%d",&graph[i]);
    }
    while(1){
        //SORTING ARRAY
        for(i=0;i<vertex_number;i  ){
            for(j=i 1;j<vertex_number;j  ){
                if(graph[i]<graph[j]){
                    temp1=graph[i];
                    graph[i]=graph[j];
                    graph[j]=temp1;
                }
            }
        }
        //IF ALL VERTEX DEGREES EQUAL 0 GRAPH EXIST
        for(i=0;i<vertex_number;i  ){
            if(graph[i]==0){
                a  ;
            }
        }
        if(a==vertex_number){
            printf(" graph exist.");
            return 0;
        }
        //NEGATIVE VERTEX DEGREE NOT EXIST
        for(i=0;i<vertex_number;i  ){
            if(graph[i]<0){
                b  ;
            }
        }
        if(b>0){
            printf("graph not exist.");
            return 0;
        }
        temp2=graph[0];
        for(i=0;i<temp2;i  ){
            graph[i]=graph[i 1];
        }
        vertex_number--;
        for(i=0;i<temp2;i  ){
            graph[i]-=1;
        }
        printf("-------------\n");
        for(i=0;i<vertex_number;i  ){
            printf("%d\n",graph[i]);
        }
    }
}

CodePudding user response：

Your have 2 issues, the exist if graph[i]-=1; is negative and the removing loop doing should be done for vertex_number and not temp2

# include <stdio.h>
int main(void) {
    int i, j, vertex_number, temp1, temp2;

    printf("Vertex Number:");
    scanf("%d", &vertex_number);
    int graph[vertex_number];
    for (i = 0; i < vertex_number; i  ){
        scanf("%d", &graph[i]);
    }
    while (1) {
        //SORTING ARRAY
        for (i = 0; i < vertex_number; i  ) {
            for (j = i 1; j < vertex_number; j  ) {
                if (graph[i] < graph[j]) {
                    temp1 = graph[i];
                    graph[i] = graph[j];
                    graph[j] = temp1;
                }
            }
        }
        //IF ALL VERTEX DEGREES EQUAL 0 GRAPH EXIST
        if (graph[0] == 0) {
            printf(" graph exist.");
            return 0;
        }
        //NEGATIVE VERTEX DEGREE NOT EXIST
        for (i = 0; i < vertex_number; i  ) {
            if (graph[i] < 0){
                printf("graph not exist.");
                return 0;
            }
        }
        temp2 = graph[0];
        vertex_number--;
        for (i = 0; i < vertex_number; i  ) { // HERE was your issue
            graph[i] = graph[i   1];
        }
        for (i = 0; i < temp2; i  ) {
            graph[i]-=1;
            if (graph[i] < 0) {
                printf("graph not exist.");
                return 0;
            }
        }
        printf("-------------\n");
        for (i = 0; i < vertex_number; i  ) {
            printf("%d\n",graph[i]);
        }
    }
}

You don't need a, if the first is null all the other are null or negative

You don't need b neither just stop on first occurence

CodePudding user response：

Not an answer, but a cleaned-up version that works follows.

The key is that it literally removes the first element from the array by advancing the pointer and reducing the size of the array. That way, we're always working with elements 0..s-1 or 0..n-1.

// Destroys the contents of the provided array.
int havel_hakimi(unsigned *degrees, size_t n) {
   while (1) {
      // Yuck
      for (size_t i=0; i<n;   i) {
        for (size_t j=i 1; j<n;   j) {
            if (degrees[i] < degrees[j]) {
                int temp = degrees[i];
                degrees[i] = degrees[j];
                degrees[j] = temp;
            }
         }
      }

      if (degrees[0] == 0)
         return 1;  // Has a simple graph.

      // Remove first element.
      unsigned s = degrees[0];
        degrees;
      --n;

      if (s > n)
         return 0;  // Invalid input!

      if (degrees[s-1] == 0)
         return 0;  // Doesn't have a simple graph.

      for (size_t i=s; i--; )
         --degrees[i];
   }
}

Tested using the following:

#include <stdio.h>

int main(void) {
   {
      unsigned degrees[] = { 6, 3, 3, 3, 3, 2, 2, 2, 2, 1, 1 };
      printf("%d\n", havel_hakimi(degrees, sizeof(degrees)/sizeof(degrees[0])));  // 1
   }

   {
      unsigned degrees[] = { 6, 5, 5, 4, 3, 2, 1 };
      printf("%d\n", havel_hakimi(degrees, sizeof(degrees)/sizeof(degrees[0])));  // 0
   }

   return 0;
}