Advertisement
welleyth

3988. Transitivity of a graph

Dec 28th, 2020
727
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 0.76 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. const int N = 101;
  5.  
  6. bool gr[N][N];
  7.  
  8. int main()
  9. {
  10.     int n,m;
  11.     scanf("%d %d",&n,&m);
  12.  
  13.     int a,b;
  14.  
  15.     for(int i = 0; i < m; ++i)
  16.     {
  17.         scanf("%d %d",&a,&b);
  18.         gr[a][b] = 1;
  19.         gr[b][a] = 1;
  20.     }
  21.  
  22.     for(int i = 1; i <= n; ++i)
  23.     {
  24.         for(int j = i + 1; j <= n; ++j)
  25.         {
  26.             for(int k = j + 1; k <= n; ++k)
  27.             {
  28.                 if((gr[i][j] && gr[j][k] && !gr[i][k])
  29.                  ||(!gr[i][j] && gr[j][k] && gr[i][k])
  30.                  ||(gr[i][j] && !gr[j][k] && gr[i][k]))
  31.                 {
  32.                     printf("NO");
  33.                     return 0;
  34.                 }
  35.             }
  36.         }
  37.     }
  38.  
  39.     printf("YES");
  40.  
  41.     return 0;
  42. }
  43.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement