fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <queue>
  5.  
  6. using namespace std;
  7.  
  8. #define maxN 100007
  9.  
  10. int n, m, k;
  11.  
  12. int sz[maxN];
  13. int par[maxN];
  14. string op[maxN];
  15. vector<int>groupPar;
  16. int groupLeadChar[maxN] = {0};
  17. vector<int>adj[maxN];
  18. int dp[maxN] = {0};
  19. vector<int>topo;
  20.  
  21. int cnt[maxN] = {0};
  22.  
  23. void make_set(int u)
  24. {
  25.     sz[u] = 1;
  26.     par[u] = u;
  27. }
  28.  
  29. int find_set(int u)
  30. {
  31.     if(par[u] == u) return u;
  32.     int p = find_set(par[u]);
  33.     par[u] = p;
  34.     return p;
  35. }
  36.  
  37. void union_set(int u, int v)
  38. {
  39.     if(u == v)
  40.         return;
  41.     if(sz[u] < sz[v])
  42.         swap(u, v);
  43.     sz[u] += sz[v];
  44.     par[v] = u;
  45. }
  46.  
  47. void readData()
  48. {
  49.     cin >> n >> k >> m;
  50.     for(int i = 1; i <= m; i++)
  51.         cin >> op[i];
  52. }
  53.  
  54. void dsu()
  55. {
  56.     for(int i = 1; i <= m; i++)
  57.     {
  58.         int equalPos = -1;
  59.         for(int j = 0; j < op[i].size(); j++)
  60.             if(op[i][j] == '=')
  61.                 equalPos = j;
  62.         if(equalPos == -1) continue;
  63.         int group1 = 0, group2 = 0;
  64.         for(int j = 0; j < equalPos; j++)
  65.             group1 = group1*10+op[i][j]-'0';
  66.         for(int j = equalPos+1; j < op[i].size(); j++)
  67.             group2 = group2*10+op[i][j]-'0';
  68.         union_set(group1, group2);
  69.     }
  70. }
  71.  
  72. void solve()
  73. {
  74.     for(int i = 1; i <= n; i++)
  75.     {
  76.         int par = find_set(i);
  77.         groupPar.push_back(par);
  78.     }
  79.     sort(groupPar.begin(), groupPar.end());
  80.     auto it = unique(groupPar.begin(), groupPar.end());
  81.     groupPar.erase(it, groupPar.end());
  82.     for(int i = 1; i <= m; i++)
  83.     {
  84.         int opPos = -1;
  85.         for(int j = 0; j < op[i].size(); j++)
  86.             if(op[i][j] == '>' || op[i][j] == '<')
  87.                 opPos = j;
  88.         if(opPos == -1)
  89.             continue;
  90.         int group1 = 0, group2 = 0;
  91.         for(int j = 0; j < opPos; j++)
  92.             group1 = group1*10+op[i][j]-'0';
  93.         for(int j = opPos+1; j < op[i].size(); j++)
  94.             group2 = group2*10+op[i][j]-'0';
  95.         group1 = find_set(group1);
  96.         group2 = find_set(group2);
  97.         if(op[i][opPos] == '<')
  98.         {
  99.             adj[group1].push_back(group2);
  100.             cnt[group2]++;
  101.         }
  102.         else
  103.         {
  104.             adj[group2].push_back(group1);
  105.             cnt[group1]++;
  106.         }
  107.     }
  108.     queue<int>q;
  109.     for(int i = 1; i <= n; i++)
  110.         if(cnt[i] == 0)
  111.             q.push(i);
  112.     while(!q.empty())
  113.     {
  114.         int cur = q.front();
  115.         q.pop();
  116.         topo.push_back(cur);
  117.         for(int v: adj[cur])
  118.         {
  119.             if(cnt[v] == 1)
  120.                 q.push(v);
  121.             cnt[v]--;
  122.         }
  123.     }
  124.     for(int u : topo)
  125.         for(int v : adj[u])
  126.             dp[v] = max(dp[v], dp[u]+1);
  127.     string ans;
  128.     for(int i = 0; i <= n; i++)
  129.         ans[i] = '|';
  130.     for(int i = topo.size()-1; i >= 0; i--)
  131.     {
  132.         int u = topo[i];
  133.         char temp = '~';
  134.         for(int v : adj[u])
  135.             temp = min(temp, ans[find_set(v)]);
  136.         if(temp == '~')
  137.         {
  138.             if(dp[u] == k-1)
  139.                 ans[u] = char('a' + k - 1);
  140.         }
  141.         else
  142.         {
  143.             if (char(dp[u] + 1 + 'a') == temp)
  144.                 ans[u] = char(dp[u] + 'a');
  145.         }
  146.     }
  147.     for(int i = 1; i <= n; i++)
  148.     {
  149.         int grp = find_set(i);
  150.         if(ans[grp] == '|')
  151.             cout << '?';
  152.         else cout << ans[grp];
  153.     }
  154. }
  155.  
  156. int main()
  157. {
  158.     ios_base::sync_with_stdio(0);
  159.     cin.tie(0);
  160.     readData();
  161.     for(int i = 1; i <= n; i++)
  162.         make_set(i);
  163.     dsu();
  164.     solve();
  165.     return 0;
  166. }
  167.  
Success #stdin #stdout 0.01s 9936KB
comments (?)
stdin
copy 
5 3 3
1>2
2>3
5=2
stdout
copy 
cba?b
https://ideone.com/YuQIn1
language:
C++14 (gcc 8.3)
created:
6 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!