Nik_Perepelov

m-покраска говном

Dec 1st, 2021
426
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. using namespace std;
  5.  
  6. class Graph {
  7.     vector<vector<int>> g;
  8.     vector<int> color;
  9.     int c;
  10.  
  11.     bool isValid(int v){
  12.         for (int i = 0; i < g[v].size(); i++){
  13.             if (color[g[v][i]] == color[v])
  14.                 return false;
  15.         }
  16.         return true;
  17.     }
  18.  
  19. public:
  20.  
  21.     Graph(int _n, int _c, vector<vector<int>> &_g){
  22.         g = _g;
  23.         color.resize(_n, -1);
  24.         c = _c;
  25.     }
  26.  
  27.     void Solve(int v = 0){
  28.         if (v == g.size()){
  29.             cout << "YES\n";
  30.             exit(0);
  31.         } else {
  32.             for (int i = 0; i < c; i++){
  33.                 color[v] = i;
  34.                 if (isValid(v))
  35.                     Solve(v + 1);
  36.                 color[v] = 0;
  37.             }
  38.         }
  39.     }
  40.  
  41. };
  42.  
  43. int main() {
  44.     int n, m, c;
  45.     cin >> n >> m >> c;
  46.     vector<vector<int>> g(n);
  47.     for (int i = 0; i < m; i++) {
  48.         int fr, to;
  49.         cin >> fr >> to;
  50.         fr--;
  51.         to--;
  52.         g[fr].emplace_back(to);
  53.         g[to].emplace_back(fr);
  54.     }
  55.  
  56.     Graph graph(n, c, g);
  57.     g.clear();
  58.  
  59.     graph.Solve();
  60.  
  61.     cout << "NO\n";
  62.  
  63. }
RAW Paste Data