ismaeil

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] = 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