Advertisement
mickypinata

FORCE-T0623A: Graph and String

Nov 22nd, 2021
572
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef tuple<int, int, int> tiii;
  5.  
  6. const int N = 500 + 5;
  7.  
  8. vector<tiii> edges;
  9. vector<int> vt;
  10. int ds[N], sz[N], isWith[N];
  11. char str[N];
  12. bool mat[N][N];
  13.  
  14. int dsFind(int u){
  15.     if(ds[u] == u){
  16.         return u;
  17.     }
  18.     int p = dsFind(ds[u]);
  19.     isWith[u] *= isWith[ds[u]];
  20.     return ds[u] = p;
  21. }
  22.  
  23. int main(){
  24.  
  25.     int nVertex, nEdge;
  26.     scanf("%d%d", &nVertex, &nEdge);
  27.     for(int u = 1; u <= nVertex; ++u){
  28.         mat[u][u] = true;
  29.         ds[u] = u;
  30.         sz[u] = 1;
  31.         isWith[u] = 1;
  32.     }
  33.     for(int i = 1; i <= nEdge; ++i){
  34.         int u, v;
  35.         scanf("%d%d", &u, &v);
  36.         mat[u][v] = true;
  37.         mat[v][u] = true;
  38.     }
  39.     for(int u = 1; u <= nVertex; ++u){
  40.         bool connectedToAll = true;
  41.         for(int v = 1; v <= nVertex; ++v){
  42.             if(!mat[u][v]){
  43.                 connectedToAll = false;
  44.                 break;
  45.             }
  46.         }
  47.         if(connectedToAll){
  48.             str[u] = 'b';
  49.         } else {
  50.             vt.push_back(u);
  51.         }
  52.     }
  53.     for(int u = 1; u < nVertex; ++u){
  54.         for(int v = u + 1; v <= nVertex; ++v){
  55.             if(binary_search(vt.begin(), vt.end(), u) && binary_search(vt.begin(), vt.end(), v)){
  56.                 edges.emplace_back(u, v, mat[u][v] ? 1 : -1);
  57.             }
  58.         }
  59.     }
  60.     for(tiii e : edges){
  61.         int u = get<0>(e);
  62.         int v = get<1>(e);
  63.         int con = get<2>(e);
  64.         int ru = dsFind(u);
  65.         int rv = dsFind(v);
  66.         if(ru != rv){
  67.             if(sz[ru] < sz[rv]){
  68.                 swap(ru, rv);
  69.                 swap(u, v);
  70.             }
  71.             ds[rv] = ru;
  72.             sz[ru] += sz[rv];
  73.             isWith[rv] = isWith[u] * isWith[v] * con;
  74.         } else if(isWith[u] == isWith[v] && con == -1 || isWith[u] != isWith[v] && con == 1){
  75.             cout << "No";
  76.             return 0;
  77.         }
  78.     }
  79.     cout << "Yes\n";
  80.     for(int u : vt){
  81.         if(isWith[u] == 1){
  82.             str[u] = 'a';
  83.         } else {
  84.             str[u] = 'c';
  85.         }
  86.     }
  87.     printf("%s", str + 1);
  88.  
  89.     return 0;
  90. }
  91.  
Advertisement
RAW Paste Data Copied
Advertisement