• API
• FAQ
• Tools
• Archive
SHARE
TWEET

# Untitled

a guest Apr 22nd, 2019 77 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.

Top