Foqrul

CycleFindingUsing String(CalingCycle)

May 7th, 2019
51
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.07 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include<stdio.h>
  3. #define lenght 15
  4.  
  5. char Name[lenght][lenght];
  6. int Path[lenght][lenght];
  7. int visit[lenght];
  8. int Node, Edge;
  9. int Len;
  10. int Case;
  11.  
  12.  
  13. int stringCompare(char st1[], char st2[])
  14. {
  15.     int i;
  16.     for (i = 0; st1[i] && st2[i]; i++) {
  17.         if (st1[i] != st2[i])
  18.             return 0;
  19.     }
  20.     if (st1[i] != st2[i])
  21.         return 0;
  22.     return 1;
  23. }
  24. void stringCopy(char dest[], char src[])
  25. {
  26.     int i;
  27.     for (i = 0; src[i]; i++)
  28.         dest[i] = src[i];
  29.     dest[i] = '\0';
  30. }
  31. int searchString(char st[]){
  32.     int i;
  33.     for (i = 0; i < Len; i++){
  34.         if (stringCompare(st, Name[i])){
  35.             return i;
  36.         }
  37.     }
  38.     return -1;
  39. }
  40. void readCase()
  41. {
  42.     int i;
  43.     int x, y;
  44.     char name1[lenght];
  45.     char name2[lenght];
  46.     Len = 0;
  47.     for (i = 0; i < Edge; i++) {
  48.         scanf("%s %s", name1, name2);
  49.         x = searchString(name1);
  50.         if (-1 == x) {
  51.             stringCopy(Name[Len], name1);
  52.             x = Len;
  53.             Len++;
  54.         }
  55.         y = searchString(name2);
  56.         if (-1 == y) {
  57.             stringCopy(Name[Len], name2);
  58.             y = Len;
  59.             Len++;
  60.         }
  61.         Path[x][y] = 1;
  62.     }
  63. }
  64. void initPath(){
  65.     int i, j;
  66.     for (i = 0; i < Node; i++)for (j = 0; j < Node; j++){
  67.             if (i == j)
  68.                 Path[i][j] = 1;
  69.             else
  70.                 Path[i][j] = 0;
  71.         }
  72. }
  73. void findAllPath()
  74. {
  75.     int i, j, k;
  76.     for (k = 0; k < Node; k++){
  77.         for (i = 0; i < Node; i++){
  78.             for (j = 0; j < Node; j++){
  79.                 if (Path[i][k] && Path[k][j]){
  80.                     Path[i][j] = 1;
  81.                 }
  82.             }
  83.         }
  84.     }
  85. }
  86.  
  87. void initvisit(){
  88.     int i;
  89.     for (i = 0; i < Node; i++){
  90.         visit[i] = 0;
  91.     }
  92. }
  93. void printCycle()
  94. {
  95.     int i, j;
  96.     if (Case > 1){
  97.         printf("\n");
  98.     }
  99.     printf("Cycle are for Case#%d\n", Case++);
  100.     initvisit();
  101.     for (i = 0; i < Node; i++){
  102.         if (0 == visit[i]){
  103.             printf("%s", Name[i]);
  104.             visit[i] = 1;
  105.             for (j = 0; j < Node; j++){
  106.                 if (!visit[j] && Path[i][j] && Path[j][i]){
  107.                     printf(", %s", Name[j]);
  108.                     visit[j] = 1;
  109.                 }
  110.             }
  111.             printf("\n");
  112.         }
  113.     }
  114. }
  115. int main()
  116. {
  117.     freopen("input.txt", "r", stdin);
  118.     Case = 1;
  119.     while (scanf("%d %d", &Node, &Edge)){
  120.         if (0 == Node && 0 == Edge)break;
  121.         initPath();
  122.         readCase();
  123.         findAllPath();
  124.         printCycle();
  125.     }
  126. }
Add Comment
Please, Sign In to add comment