Nik_Perepelov

ислам

Dec 1st, 2021 (edited)
215
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4. using namespace std;
  5. int n;
  6. vector<vector<int>> g;
  7. vector<int> color;
  8. bool valid(int v) {
  9.     for (int i = 0; i < g[v].size(); i++) {
  10.         if (color[g[v][i]] == color[v]) {
  11.             return false;
  12.         }
  13.  
  14.     }
  15.     return true;
  16. }
  17. void coloring( int v, int c) {
  18.     //c = 0;
  19.     if (v == n) {
  20.         cout << "YES";
  21.         exit(0);
  22.     }
  23.     else {
  24.         for (int i = 0; i < c; i++) {
  25.             color[v] = i;
  26.             if (valid(v) == true) {
  27.                 coloring( v + 1, c);
  28.             }
  29.                 color[v] = 0;
  30.         }
  31.     }
  32. }
  33.  
  34.  
  35. int main() {
  36.     int m, c;
  37.     cin >> n >> m >> c;
  38.     g.resize(n);
  39.     for (int i = 0; i < m; i++) {
  40.         int s, f;
  41.         cin >> s >> f;
  42.         s--;
  43.         f--;
  44.         g[s].push_back(f);
  45.         g[f].push_back(s);
  46.  
  47.     }
  48.     color.resize(n, -1);
  49.     coloring( 0, c);
  50.     cout << "NO";
  51. }
  52.  
  53.  
  54.  
RAW Paste Data