SHARE
TWEET

Untitled

a guest Apr 22nd, 2019 75 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include <cstdio>
  3. #include <iostream>
  4. #include <cmath>
  5. #include <algorithm>
  6.  
  7. using namespace std;
  8.  
  9. const int N = 110;
  10.  
  11. int graph[N][N];
  12. int n;
  13. int colour[N];
  14.  
  15. void dfs(int v) {
  16.     for (int i = 0; i < n; i++) {
  17.         int to = graph[v][i];
  18.         if (to == 0) {
  19.             continue;
  20.         }
  21.         if (colour[i] == -1) {
  22.             colour[i] = 1 - colour[v];
  23.             dfs(i);
  24.         }
  25.     }
  26. }
  27.  
  28. bool possible() {
  29.     for (int i = 0; i < n; i++) {
  30.         for (int j = 0; j < n; j++) {
  31.             if (i == j) {
  32.                 continue;
  33.             }
  34.             if (graph[i][j] == 1 && colour[i] == colour[j]) {
  35.                 return false;
  36.             }
  37.         }
  38.     }
  39.     return true;
  40. }
  41.  
  42. int main() {
  43.     freopen("input.txt", "r", stdin);
  44.     freopen("output.txt", "w", stdout);
  45.     scanf("%d", &n);
  46.     for (int i = 0; i < n; i++) {
  47.         for (int j = 0; j < n; j++) {
  48.             scanf(" %d", &graph[i][j]);
  49.         }
  50.     }
  51.     for (int i = 0; i < n; i++) {
  52.         colour[i] = -1;
  53.     }
  54.     for (int i = 0; i < n; i++) {
  55.         if (colour[i] == -1) {
  56.             dfs(i);
  57.             colour[i] = 0;
  58.         }
  59.     }
  60.     if (possible()) {
  61.         printf("YES");
  62.     }
  63.     else {
  64.         printf("NO");
  65.     }
  66.     return 0;
  67. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top