 # ff

May 9th, 2021
862
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. /*********************
2. * My Solution Explain:
3. *
4. * 1) We can notice that the number of colors is two only.
5. *
6. * 2) We can simplify the problem to:
7. *    - Check if the Graph is Biparatite Graph.
8. *
9. * 3) Biparatite Graph is:
10. *    - The Graph that has n vertices and we can separate
11. *      the graph into two disjoint sets V1 ,V2.
12. *    - Each node exists in ONE of the sets.
13. *    - No two neighbour nodes are in the same set.
14. *
15. * 4) The problem is coloring the graph by using two colors
16. *    and no two neighbour nodes have the same color.
17. *    So the problem is check the graph is Biparatite or not.
18. *
19. * 5) We can check the Biparatite Property by using BFS:
20. *    - Make queue for travers the graph by levels.
21. *    - Make an array[N] that store the color of the node.
22. *    - The colors are:
23. *       # -1: (init) The node isn't colored yet.
24. *       #  0: First color.
25. *       #  1: Second color.
26. *    - Each node color all its neighbour nodes in differint color.
27. *    - If the neighbour node is colored before => we check if it has
28. *      the same color or not.
29. *    - If it has tha same color => we say the graph isn't Biparatite.
30. *
31. * 6) Time Complexity:
32. *
33. *
34. * Thanks for the great competition AmesCom.
35. *
36. * Author: Ismaeil Al-refaey.
37. ***************************/
38. #include <bits/stdc++.h>
39.
40. using namespace std;
41.
42. typedef vector< int > vi;
43.
44. /// --- Graph Adjacency List --- ///
45. vector< vi > al;
46. int n ,m;
47.
48. /// --- Initialize new test case --- ///
49. void init()
50. {
51.     al.assign(n ,vi());
52. }
53.
54. /// --- Function return true if the Graph is Biparatite else return false --- ///
55. bool checkBiparatite()
56. {
57.     /// --- Biparatite Checker --- ///
58.     bool isBiparatite = true;
59.
60.     /// --- queue for travers the graph --- ///
61.     queue< int > q;
62.     q.push(0);
63.
64.     /// --- vector have the colors of nodes --- ///
65.     vi color(n ,-1);
66.     color = 0;
67.
68.     /// --- BFS --- ///
69.     while( !q.empty() && isBiparatite )
70.     {
71.         int u = q.front(); q.pop();
72.
73.         /// --- Check all neighbour nodes --- ///
74.         for(int v : al[u])
75.         {
76.             if( color[v] == -1 )
77.             {
78.                 /// --- Color the neighbour nodes in different color --- ///
79.                 color[v] = 1 - color[u];
80.                 q.push(v);
81.             }
82.
83.             /// --- Update Biparatite Checker --- ///
84.             isBiparatite &= (color[v] != color[u]);
85.         }
86.     }
87.
88.     /// --- return the result --- ///
89.     return isBiparatite;
90. }
91.
92. void Solve()
93. {
94.     init();
95.
96.     /// --- Input --- ///
97.     scanf("%d" ,&m);
98.     for(int i = 0 ; i < m ; i++)
99.     {
100.         int u; scanf("%d" ,&u);
101.         int v; scanf("%d" ,&v);
102.
103.         /// --- Un_Directed Graph: we can go (u <-> v) --- ///
104.         /// --- We add new neighbour
105.         al[u].push_back(v);
106.         al[v].push_back(u);
107.     }
108.
109.     /// --- Check if the Graph is Biparatite Graph --- ///
110.     bool isBi = checkBiparatite();
111.
112.     /// --- Outpus --- ///
113.     puts(isBi ? "BICOLORABLE." : "NOT BICOLORABLE.");
114. }
115.
116. int main()
117. {
118.     /// --- Test Cases --- ///
119.     while( scanf("%d" ,&n) , n != 0 ) Solve();
120.     return 0;
121. }
122.
RAW Paste Data