fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define task ""
  3. #define ii pair<int, int>
  4. #define pli pair<long long, int>
  5. #define ll long long
  6. #define ld long double
  7. #define fi first
  8. #define se second
  9. #define faster ios_base::sync_with_stdio(false); cin.tie(nullptr);
  10. #define F if(fopen(task".inp","r")){ freopen(task".inp","r",stdin); freopen(task".out","w",stdout); }
  11.  
  12. using namespace std;
  13.  
  14. const int Q = 1e6 + 21;
  15. const int N = 1e5 + 21;
  16. const int LOG = 20;
  17. const int mod = 1e9 + 7;
  18. const int inf = 1e9 + 7;
  19. const int dx[] = {0, 0, 1, -1};
  20. const int dy[] = {1, -1, 0, 0};
  21.  
  22. int n, m;
  23. vector<int> adj[N];
  24.  
  25. int deg[N];
  26. int cur_deg[N];
  27.  
  28. bool rem[N];
  29.  
  30. int color[N];
  31. int best_k, best[N];
  32.  
  33. int vis[N], vis_timer = 0;
  34. int in_nei[N], nei_timer = 0;
  35.  
  36. mt19937 rng(1337);
  37.  
  38.  
  39. bool check_bipartite()
  40. {
  41.     if(m == 0)
  42.     {
  43.         best_k = 1;
  44.         for(int i = 1; i <= n; i++) best[i] = 1;
  45.         return true;
  46.     }
  47.  
  48.     for(int i = 1; i <= n; i++) color[i] = 0;
  49.  
  50.     for(int i = 1; i <= n; i++)
  51.     {
  52.         if(color[i] != 0) continue;
  53.         color[i] = 1;
  54.         queue<int> q;
  55.         q.push(i);
  56.         while(!q.empty())
  57.         {
  58.             int u = q.front();
  59.             q.pop();
  60.             for(int v : adj[u])
  61.             {
  62.                 if(color[v] == 0)
  63.                 {
  64.                     color[v] = 3 - color[u];
  65.                     q.push(v);
  66.                 }
  67.                 else if(color[v] == color[u])
  68.                 {
  69.                     return false;
  70.                 }
  71.             }
  72.         }
  73.     }
  74.  
  75.     best_k = 2;
  76.     for(int i = 1; i <= n; i++) best[i] = color[i];
  77.     return true;
  78. }
  79.  
  80.  
  81. bool kempe_color(int u)
  82. {
  83.     vector<int> nei;
  84.     ++nei_timer;
  85.     for(int v : adj[u])
  86.     {
  87.         if(color[v] >= 1 && color[v] <= 4)
  88.         {
  89.             nei.push_back(v);
  90.             in_nei[v] = nei_timer;
  91.         }
  92.     }
  93.  
  94.     int last_w = -1, last_mask = -1;
  95.     vector<int> q;
  96.     q.reserve(n);
  97.  
  98.     for(int step = 0; step < 45; step++)
  99.     {
  100.         int cnt[5] = {0, 0, 0, 0, 0};
  101.         int who[5][2];
  102.  
  103.         for(int v : nei)
  104.         {
  105.             int c = color[v];
  106.             if(c >= 1 && c <= 4)
  107.             {
  108.                 if(cnt[c] < 2) who[c][cnt[c]] = v;
  109.                 cnt[c]++;
  110.             }
  111.         }
  112.  
  113.         for(int c = 1; c <= 4; c++)
  114.         {
  115.             if(cnt[c] == 0)
  116.             {
  117.                 color[u] = c;
  118.                 return true;
  119.             }
  120.         }
  121.  
  122.  
  123.         vector<ii> pairs;
  124.         for(int c1 = 1; c1 <= 4; c1++)
  125.         {
  126.             if(cnt[c1] != 1) continue;
  127.             for(int c2 = c1 + 1; c2 <= 4; c2++)
  128.             {
  129.                 if(cnt[c2] == 1)
  130.                     pairs.push_back({c1, c2});
  131.             }
  132.             for(int c2 = 1; c2 <= 4; c2++)
  133.             {
  134.                 if(cnt[c2] >= 2)
  135.                     pairs.push_back({c1, c2});
  136.             }
  137.         }
  138.         shuffle(pairs.begin(), pairs.end(), rng);
  139.  
  140.         struct StepBMove { int c1, c2, w; };
  141.         vector<StepBMove> stepB_moves;
  142.         vector<ii> deferred_pairs;
  143.  
  144.         const int SMALL_LIMIT = 64;
  145.  
  146.  
  147.         for(auto &pr : pairs)
  148.         {
  149.             int c1 = pr.fi, c2 = pr.se;
  150.             int start_v = who[c1][0];
  151.  
  152.             ++vis_timer;
  153.             q.clear();
  154.             q.push_back(start_v);
  155.             vis[start_v] = vis_timer;
  156.  
  157.             int reached_cnt = 0;
  158.             for(size_t head = 0; head < q.size(); head++)
  159.             {
  160.                 int x = q[head];
  161.                 for(int y : adj[x])
  162.                 {
  163.                     int cy = color[y];
  164.                     if((cy == c1 || cy == c2) && vis[y] != vis_timer)
  165.                     {
  166.                         vis[y] = vis_timer;
  167.                         q.push_back(y);
  168.                         if(in_nei[y] == nei_timer && cy == c2)
  169.                             reached_cnt++;
  170.                     }
  171.                 }
  172.                 if(reached_cnt == cnt[c2] || (int)q.size() > SMALL_LIMIT)
  173.                     break;
  174.             }
  175.  
  176.             if(reached_cnt == cnt[c2])
  177.                 continue;
  178.  
  179.             if((int)q.size() <= SMALL_LIMIT)
  180.             {
  181.                 if(reached_cnt == 0)
  182.                 {
  183.                     for(int x : q) color[x] = (color[x] == c1 ? c2 : c1);
  184.                     color[u] = c1;
  185.                     return true;
  186.                 }
  187.                 else if(cnt[c2] == 2 && reached_cnt == 1)
  188.                 {
  189.                     int w_unreached = (vis[who[c2][0]] == vis_timer) ? who[c2][1] : who[c2][0];
  190.                     stepB_moves.push_back({c1, c2, w_unreached});
  191.                 }
  192.             }
  193.             else
  194.             {
  195.                 deferred_pairs.push_back(pr);
  196.             }
  197.         }
  198.  
  199.  
  200.         for(auto &pr : deferred_pairs)
  201.         {
  202.             int c1 = pr.fi, c2 = pr.se;
  203.             int start_v = who[c1][0];
  204.  
  205.             ++vis_timer;
  206.             q.clear();
  207.             q.push_back(start_v);
  208.             vis[start_v] = vis_timer;
  209.  
  210.             int reached_cnt = 0;
  211.             for(size_t head = 0; head < q.size(); head++)
  212.             {
  213.                 int x = q[head];
  214.                 for(int y : adj[x])
  215.                 {
  216.                     int cy = color[y];
  217.                     if((cy == c1 || cy == c2) && vis[y] != vis_timer)
  218.                     {
  219.                         vis[y] = vis_timer;
  220.                         q.push_back(y);
  221.                         if(in_nei[y] == nei_timer && cy == c2)
  222.                             reached_cnt++;
  223.                     }
  224.                 }
  225.                 if(reached_cnt == cnt[c2])
  226.                     break;
  227.             }
  228.  
  229.             if(reached_cnt == 0)
  230.             {
  231.                 for(int x : q) color[x] = (color[x] == c1 ? c2 : c1);
  232.                 color[u] = c1;
  233.                 return true;
  234.             }
  235.             else if(cnt[c2] == 2 && reached_cnt == 1)
  236.             {
  237.                 int w_unreached = (vis[who[c2][0]] == vis_timer) ? who[c2][1] : who[c2][0];
  238.                 stepB_moves.push_back({c1, c2, w_unreached});
  239.             }
  240.         }
  241.  
  242.  
  243.         if(stepB_moves.empty()) break;
  244.  
  245.         shuffle(stepB_moves.begin(), stepB_moves.end(), rng);
  246.         StepBMove chosen = stepB_moves[0];
  247.         for(auto &mv : stepB_moves)
  248.         {
  249.             int mask = (1 << mv.c1) | (1 << mv.c2);
  250.             if(mv.w != last_w || mask != last_mask)
  251.             {
  252.                 chosen = mv;
  253.                 break;
  254.             }
  255.         }
  256.  
  257.         ++vis_timer;
  258.         q.clear();
  259.         q.push_back(chosen.w);
  260.         vis[chosen.w] = vis_timer;
  261.         for(size_t head = 0; head < q.size(); head++)
  262.         {
  263.             int x = q[head];
  264.             for(int y : adj[x])
  265.             {
  266.                 int cy = color[y];
  267.                 if((cy == chosen.c1 || cy == chosen.c2) && vis[y] != vis_timer)
  268.                 {
  269.                     vis[y] = vis_timer;
  270.                     q.push_back(y);
  271.                 }
  272.             }
  273.         }
  274.         for(int x : q) color[x] = (color[x] == chosen.c1 ? chosen.c2 : chosen.c1);
  275.  
  276.         last_w = chosen.w;
  277.         last_mask = (1 << chosen.c1) | (1 << chosen.c2);
  278.     }
  279.  
  280.     return false;
  281. }
  282.  
  283. void solve()
  284. {
  285.     cin >> n >> m;
  286.  
  287.     best_k = inf;
  288.  
  289.     for(int i = 1; i <= n; i++)
  290.     {
  291.         adj[i].clear();
  292.         deg[i] = 0;
  293.         best[i] = 0;
  294.     }
  295.  
  296.     for(int i = 1; i <= m; i++)
  297.     {
  298.         int u, v;
  299.         cin >> u >> v;
  300.         if(u == v) continue;
  301.  
  302.         adj[u].push_back(v);
  303.         adj[v].push_back(u);
  304.     }
  305.  
  306.  
  307.     for(int i = 1; i <= n; i++)
  308.     {
  309.         sort(adj[i].begin(), adj[i].end());
  310.         adj[i].erase(unique(adj[i].begin(), adj[i].end()), adj[i].end());
  311.         deg[i] = adj[i].size();
  312.     }
  313.  
  314.     if(check_bipartite())
  315.     {
  316.         cout << best_k << '\n';
  317.         for(int i = 1; i <= n; i++) cout << best[i] << " ";
  318.         cout << '\n';
  319.         return;
  320.     }
  321.  
  322.     clock_t start_time = clock();
  323.     vector<bool> used(n + 2, false);
  324.  
  325.     while(best_k > 4 && (double)(clock() - start_time) / CLOCKS_PER_SEC < 2.6)
  326.     {
  327.         for(int i = 1; i <= n; i++)
  328.         {
  329.             cur_deg[i] = deg[i];
  330.             rem[i] = false;
  331.             color[i] = 0;
  332.         }
  333.  
  334.  
  335.         priority_queue<pli, vector<pli>, greater<pli>> pq;
  336.  
  337.         for(int i = 1; i <= n; i++)
  338.         {
  339.             pq.push({(1LL * cur_deg[i] << 30) | (rng() & 0x3FFFFFFF), i});
  340.         }
  341.  
  342.         vector<int> order;
  343.         order.reserve(n);
  344.  
  345.         while(!pq.empty())
  346.         {
  347.             auto p = pq.top();
  348.             pq.pop();
  349.  
  350.             int u = p.se;
  351.             if(rem[u]) continue;
  352.  
  353.             rem[u] = true;
  354.             order.push_back(u);
  355.  
  356.             for(int v : adj[u])
  357.             {
  358.                 if(!rem[v])
  359.                 {
  360.                     cur_deg[v]--;
  361.                     pq.push({(1LL * cur_deg[v] << 30) | (rng() & 0x3FFFFFFF), v});
  362.                 }
  363.             }
  364.         }
  365.  
  366.         reverse(order.begin(), order.end());
  367.  
  368.         int cur_k = 0;
  369.  
  370.         for(int u : order)
  371.         {
  372.             int mask = 0;
  373.             for(int v : adj[u])
  374.                 if(color[v] >= 1 && color[v] <= 4)
  375.                     mask |= (1 << color[v]);
  376.  
  377.             int chosen_c = 0;
  378.             for(int c = 1; c <= 4; c++)
  379.             {
  380.                 if(!(mask & (1 << c)))
  381.                 {
  382.                     chosen_c = c;
  383.                     break;
  384.                 }
  385.             }
  386.  
  387.             if(chosen_c > 0)
  388.             {
  389.                 color[u] = chosen_c;
  390.             }
  391.             else if(!kempe_color(u))
  392.             {
  393.  
  394.                 for(int v : adj[u])
  395.                     if(color[v] > 0) used[color[v]] = true;
  396.                 for(int c = 1; c <= n; c++)
  397.                 {
  398.                     if(!used[c])
  399.                     {
  400.                         color[u] = c;
  401.                         break;
  402.                     }
  403.                 }
  404.                 for(int v : adj[u])
  405.                     if(color[v] > 0) used[color[v]] = false;
  406.             }
  407.  
  408.             cur_k = max(cur_k, color[u]);
  409.             if(cur_k >= best_k) break;
  410.         }
  411.  
  412.         if(cur_k < best_k)
  413.         {
  414.             best_k = cur_k;
  415.             for(int i = 1; i <= n; i++)
  416.                 best[i] = color[i];
  417.         }
  418.     }
  419.  
  420.     cout << best_k << '\n';
  421.     for(int i = 1; i <= n; i++)
  422.         cout << best[i] << " ";
  423.     cout << '\n';
  424. }
  425.  
  426. signed main()
  427. {
  428.     faster;
  429.     F;
  430.  
  431.     int test = 1;
  432.  
  433.  
  434.     while(test--)
  435.     {
  436.         solve();
  437.     }
  438.  
  439.     cerr << "Time elapsed: " << (1.0 * clock() / CLOCKS_PER_SEC) << " s.\n";
  440.  
  441.     return 0;
  442. }
  443.  
Success #stdin #stdout #stderr 0.01s 8344KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
stderr
copy 
Time elapsed: 0.006958 s.
https://ideone.com/GmsKm1
language:
C++ (gcc 8.3)
created:
19 hours 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!