fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // Problem: Graph with n nodes and m edges
  5. // k nodes are "special" - cannot add edges between special nodes
  6. // Find maximum edges we can add without connecting special nodes
  7.  
  8. struct DSU {
  9.     vector<int> p;   // parent array
  10.     vector<int> sz;  // size of each component
  11.  
  12.     DSU(int n = 0) {
  13.         init(n);
  14.     }
  15.  
  16.     void init(int n) {
  17.         p.resize(n + 1);
  18.         sz.assign(n + 1, 1);
  19.         iota(p.begin(), p.end(), 0);  // each node is its own parent initially
  20.     }
  21.  
  22.     // Find root of node u with path compression
  23.     int find(int u) {
  24.         while (p[u] != u) {
  25.             p[u] = p[p[u]];  // compress path
  26.             u = p[u];
  27.         }
  28.         return u;
  29.     }
  30.  
  31.     // Merge two components using union by size
  32.     void merge(int u, int v) {
  33.         u = find(u);
  34.         v = find(v);
  35.         if (u == v) return;
  36.  
  37.         if (sz[u] < sz[v]) swap(u, v);  // make u the larger component
  38.         p[v] = u;
  39.         sz[u] += sz[v];
  40.     }
  41. };
  42.  
  43. class Solution {
  44. public:
  45.     long long maxEdgesToAdd(int n, vector<array<int, 2>>& e, vector<int>& sp) {
  46.         // Build connected components from existing edges
  47.         DSU d(n);
  48.         for (auto& x : e) {
  49.             d.merge(x[0], x[1]);
  50.         }
  51.  
  52.         // Mark which components contain special nodes
  53.         // (components inherit "special" property from their nodes)
  54.         vector<bool> isSp(n + 1, false);
  55.         for (int x : sp) {
  56.             isSp[d.find(x)] = true;
  57.         }
  58.  
  59.         // Collect all component roots
  60.         vector<int> comp;
  61.         for (int i = 1; i <= n; i++) {
  62.             if (d.find(i) == i) {
  63.                 comp.push_back(i);
  64.             }
  65.         }
  66.  
  67.         // Max edges in a complete graph of k nodes: k*(k-1)/2
  68.         auto maxE = [](long long k) {
  69.             return k * (k - 1) / 2;
  70.         };
  71.  
  72.         // If no special nodes, merge everything into one complete graph
  73.         if (sp.empty()) {
  74.             return maxE(n) - (long long)e.size();
  75.         }
  76.  
  77.         // Find size of largest special component and total non-special nodes
  78.         long long maxSp = 0;
  79.         long long totNonSp = 0;
  80.  
  81.         for (int r : comp) {
  82.             long long s = d.sz[r];
  83.  
  84.             if (isSp[r]) {
  85.                 maxSp = max(maxSp, s);
  86.             } else {
  87.                 totNonSp += s;
  88.             }
  89.         }
  90.  
  91.         // Greedy strategy: 
  92.         // - Merge ALL non-special components with the LARGEST special component
  93.         //   (this maximizes edges since we create one big component)
  94.         // - Keep other special components isolated (can't connect them anyway)
  95.         long long maxPos = 0;
  96.  
  97.         // Count edges in the merged super-component
  98.         // (largest special component + all non-special nodes)
  99.         maxPos += maxE(maxSp + totNonSp);
  100.  
  101.         // Add edges within other special components (they stay separate)
  102.         bool skip = false;
  103.         for (int r : comp) {
  104.             if (!isSp[r]) continue;
  105.  
  106.             long long s = d.sz[r];
  107.  
  108.             // Skip the largest special component (already counted above)
  109.             if (s == maxSp && !skip) {
  110.                 skip = true;
  111.                 continue;
  112.             }
  113.  
  114.             // Each remaining special component forms its own complete graph
  115.             maxPos += maxE(s);
  116.         }
  117.  
  118.         // Answer = max possible edges - edges already present
  119.         return maxPos - (long long)e.size();
  120.     }
  121. };
  122.  
  123. int main() {
  124.     ios::sync_with_stdio(false);
  125.     cin.tie(nullptr);
  126.  
  127.     int n, m, k;
  128.     cin >> n >> m >> k;
  129.  
  130.     // Input: m edges
  131.     vector<array<int, 2>> e(m);
  132.     for (int i = 0; i < m; i++) {
  133.         cin >> e[i][0] >> e[i][1];
  134.     }
  135.  
  136.     // Input: k special nodes
  137.     vector<int> sp(k);
  138.     for (int i = 0; i < k; i++) {
  139.         cin >> sp[i];
  140.     }
  141.  
  142.     Solution sol;
  143.     cout << sol.maxEdgesToAdd(n, e, sp) << "\n";
  144.  
  145.     return 0;
  146. }
Runtime error #stdin #stdout #stderr 0.01s 5308KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc
https://ideone.com/lS7t36
language:
C++14 (gcc 8.3)
created:
115 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!