Nik_Perepelov

Раскраска графа говном

Dec 1st, 2021
681
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. struct DSU{
  7.     int cnt;
  8.     vector<int> parent;
  9.     vector<vector<int>> component;
  10.  
  11.     explicit DSU(int n){
  12.         parent.resize(n);
  13.         component.resize(n);
  14.         for (int i = 0; i < n; i++){
  15.             parent[i] = i;
  16.             component[i].emplace_back(i);
  17.         }
  18.         cnt = n;
  19.     }
  20.  
  21.     int getParent(int v){
  22.         if (parent[v] == v)
  23.             return v;
  24.         return parent[v] = getParent(parent[v]);
  25.     }
  26.  
  27.     int unionSets(int v, int u){
  28.         v = getParent(v);
  29.         u = getParent(u);
  30.         if (u != v){
  31.             parent[u] = v;
  32.             component[v].insert(component[v].end(), component[u].begin(), component[u].end());
  33.             component[u].clear();
  34.             cnt--;
  35.         }
  36.     }
  37.  
  38.  
  39.     int getComponentsCnt() const{
  40.         return cnt;
  41.     }
  42.  
  43. };
  44.  
  45. class Graph {
  46.     vector<vector<bool>> g;
  47.     vector<int> color;
  48.     vector<bool> used;
  49.     DSU *dsu;
  50.  
  51. public:
  52.  
  53.     Graph(vector<vector<bool>> &_g, vector<int> &_color, DSU *_dsu) {
  54.         g = _g;
  55.         color = _color;
  56.         used.resize(g.size());
  57.         dsu = _dsu;
  58.     }
  59.  
  60.     int countEdge() {
  61.         int cnt = 0;
  62.         for (int i = 0; i < g.size(); i++) {
  63.             for (int j = 0; j < g.size(); j++) {
  64.                 if (i == j)
  65.                     continue;
  66.                 if (color[i] != color[j] && !g[i][j]) {
  67.                     g[i][j] = true;
  68.                     g[j][i] = true;
  69.                     dsu->unionSets(i, j);
  70.                     cnt++;
  71.                 }
  72.             }
  73.         }
  74.         return cnt;
  75.     }
  76.  
  77. };
  78.  
  79.  
  80.  
  81. int main() {
  82.     int queries;
  83.     cin >> queries;
  84.     for (int query = 0; query < queries; query++) {
  85.         int n, m, p, k;
  86.         cin >> n >> m >> p >> k;
  87.         vector<vector<bool>> g(n, vector<bool>(n));
  88.         vector<int> color(n);
  89.         DSU dsu(n);
  90.         for (int i = 0; i < n; i++)
  91.             cin >> color[i];
  92.         for (int i = 0; i < m; i++) {
  93.             int fr, to;
  94.             cin >> fr >> to;
  95.             fr--;
  96.             to--;
  97.             g[fr][to] = true;
  98.             g[to][fr] = true;
  99.             dsu.unionSets(fr, to);
  100.         }
  101.  
  102.         if (dsu.getComponentsCnt() - 1 > p){
  103.             cout << "N\n";
  104.             continue;
  105.         }
  106.         // проверить, можно ли соединить разные компоненты связности
  107.  
  108.  
  109.  
  110.  
  111.         Graph graph(g, color, &dsu);
  112.  
  113.         if (graph.countEdge() >= p && dsu.getComponentsCnt() == 1) {
  114.             cout << "Y\n";
  115.         } else {
  116.             cout << "N\n";
  117.         }
  118.     }
  119.  
  120. }
RAW Paste Data