도와줘요 이글루스 지식인!! 그래프의 연결 및 이어쓰기 판정

어찌어찌 전번의 문제는 해결 가능했습니다(꾸벅)

그래서 이번 과제의 마지막 문제인데, 이번에는 print_graph_memory()를 참고해서 그래프가 연결인지 아닌지, 또 연결일 때는 이어쓰기(一筆書き)가 가능한지의 여부를 판정하는 프로그램을 만들라는데......

이건 또 어찌 해야하는 걸까요...(먼산)

참고로 판정해야 하는 파일은

p 10 15
e 2 4
e 4 6
e 6 8
e 8 10
e 10 2
e 2 6
e 6 10
e 10 4
e 4 8
e 8 2
e 1 3
e 3 5
e 5 7
e 7 9
e 9 1

이런 느낌입니다.

...다른 사람걸 봤는데 이렇더군요. 그런데 이게 왜 되는지 잘 모르겠네요...(먼산)

void print_graph_memory(graph *g){
   vindex v;
   int a=0, a2=0, breach, b, c, sum=0, ren=0, ip=0, e[g->vertex_num], f, h=0;

   FILE *dotfp = fopen("graph.dot","w+");

   fprintf(dotfp, "digraph G {\n");
   fprintf(dotfp, "  size=\"14,10\";\n");
   fprintf(dotfp, "  node[fontsize=10,height=0.01,width=0.01];\n");
   fprintf(dotfp, "  edge[len=3.0];\n\n");
     
   for(v = 0; v < g->vertex_num; v++){
         edgecell *edge;
         if( a2 >= a || a2 == 0){
            breach = v;
            a2 = a;
         }
         a = 0;
      for(edge = g->vtop[v].adjlist; edge != NULL; edge = edge->next){
     fprintf(dotfp, "  %d -> %d;\n", v + 1, edge->destination+1);
         a++;
      }
   }
   fprintf(dotfp, "}\n");
   fclose(dotfp);
   system("neato -Tps graph.dot > graph.ps");

   for(f = 0 ; f < g -> vertex_num; f++){
         e[f] = 0;
   }
   b = breach;
   while(1){
         edgecell *edge;
         edge = g->vtop[b].adjlist;
         if(edge == NULL){
             break;
         }
         e[b] = 1;
         sum = 0;
         for(f = 0 ; f < g -> vertex_num; f++)
              sum = sum + e[f];
         if(sum == g-> vertex_num && b == breach){
              ren = 1;
              if( h == g -> edge_num && b == breach){
                    ip = 1;
                    break;
              }
              else if(h > g -> edge_num)
                    break;
         }
         c = edge -> destination;
         if(edge->next != NULL || h >= g -> vertex_num  * g -> edge_num)
              g->vtop[b].adjlist = edge ->next;
         b = c;
         h++;

   }
   if(ren){
         printf("連結です。");
         if(ip)
             printf("且つ、一筆書き可能です\n");
         else
             printf("しかし、一筆書きは出来ません\n");
   }
   else
         printf("連結じゃないです\n");
}

덧글

[najlepsze tabletki n]

좋은 아이디어, 이런 글 더 많이