fork download 
  1. #include <iostream>
  2. #include <vector>
  3. #include <unordered_map>
  4. using namespace std;
  5.  
  6. void dfs(int src, vector<vector<int>> &graph, vector<int> &vis, vector<int> &comp_id, int comp) {
  7.     vis[src] = 1;
  8.     comp_id[src] = comp;
  9.     for (auto &nbr : graph[src]) {
  10.         if (!vis[nbr]) {
  11.             dfs(nbr, graph, vis, comp_id, comp);
  12.         }
  13.     }
  14. }
  15.  
  16. void dfs1(int src, vector<vector<int>> &graph, vector<int> &vis) {
  17.     vis[src] = 1;
  18.     for (auto &nbr : graph[src]) {
  19.         if (!vis[nbr]) {
  20.             dfs1(nbr, graph, vis);
  21.         }
  22.     }
  23. }
  24.  
  25. int main() {
  26.     int t;
  27.     cin >> t;
  28.  
  29.     while (t--) {
  30.         int n, m1, m2;
  31.         cin >> n >> m1 >> m2;
  32.  
  33.         vector<vector<int>> graphF(n + 1);
  34.         vector<vector<int>> graphG(n + 1);
  35.         vector<pair<int, int>> fEdges;
  36.  
  37.         // Read Graph F
  38.         for (int i = 0; i < m1; ++i) {
  39.             int u, v;
  40.             cin >> u >> v;
  41.             fEdges.push_back({u, v});
  42.         }
  43.  
  44.         // Read Graph G
  45.         for (int i = 0; i < m2; ++i) {
  46.             int u, v;
  47.             cin >> u >> v;
  48.             graphG[u].push_back(v);
  49.             graphG[v].push_back(u);
  50.         }
  51.  
  52.         // Compute component IDs for graph G
  53.         vector<int> comp_id(n + 1, 0);
  54.         vector<int> vis(n + 1, 0);
  55.         int comp = 1;
  56.         for (int i = 1; i <= n; ++i) {
  57.             if (!vis[i]) {
  58.                 dfs(i, graphG, vis, comp_id, comp);
  59.                 comp++;
  60.             }
  61.         }
  62.  
  63.         int count = 0;
  64.  
  65.         // Add only valid edges from F (within same G-component)
  66.         for (auto &[u, v] : fEdges) {
  67.             if (comp_id[u] == comp_id[v]) {
  68.                 graphF[u].push_back(v);
  69.                 graphF[v].push_back(u);
  70.             } else {
  71.                 count++; // Bad edge
  72.             }
  73.         }
  74.  
  75.         // For each G component, count number of F components
  76.         unordered_map<int, int> componentFreq;
  77.         vector<int> vis1(n + 1, 0);
  78.  
  79.         for (int i = 1; i <= n; ++i) {
  80.             if (!vis1[i]) {
  81.                 dfs1(i, graphF, vis1);
  82.                 componentFreq[comp_id[i]]++;
  83.             }
  84.         }
  85.  
  86.         // Add (freq - 1) for each disconnected part inside same G-component
  87.         for (auto &[cid, freq] : componentFreq) {
  88.             count += (freq - 1);
  89.         }
  90.  
  91.         cout << count << "\n";
  92.     }
  93.  
  94.     return 0;
  95. }
  96.  
Success #stdin #stdout 0s 5316KB
comments (?)
stdin 
5
3 2 1
1 2
2 3
1 3
2 1 1
1 2
1 2
3 2 0
3 2
1 2
1 0 0
3 3 1
1 2
1 3
2 3
1 2
stdout 
3
0
2
0
2
https://ideone.com/qp6Ykv
language:
C++ (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!