1013. Battle Over Cities (25)-白红宇

1013. Battle Over Cities (25)

阅读量：797 次

发布时间：2023-03-23

本文共 1797 字，大约阅读时间需要 5 分钟。

去掉某一个城市后，剩下的城市需要额外增加的道路数量取决于这些城市的连通性。为了解决这个问题，我们可以使用并查集（Union-Find）数据结构来高效地处理城市之间的连通性问题。

方法思路

初始化：每个城市最初都是自己的集合。

处理边：对于每条不涉及目标城市q的边，使用并查集将两个城市合并。

统计连通分量：找到所有的根节点，统计连通分量的数量。

计算边数：连通分量的数量减去1即为需要添加的边数。

这种方法利用并查集的高效操作（路径压缩和按秩合并），确保在处理大规模数据时依然能够快速得出结果。

解决代码

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         using namespace std;#define INF 0x7FFFFFFFvector
          
           
            > map;vector
            
              mcity;vector
             
               check;int n, m, k;void initial() { for (int i = 0; i < n; i++) { mcity[i] = i; }}void compressTop(int xParent, int x) { if (mcity[x] != xParent) { compressTop(xParent, mcity[x]); mcity[x] = xParent; }}int findSet(int x) { if (mcity[x] != x) { int xParent = findSet(mcity[x]); compressTop(xParent, x); } return mcity[x];}void unionSet(int x, int y) { int a = findSet(x); int b = findSet(y); mcity[a] = b;}int main() { scanf("%d %d %d", &n, &m, &k); map.resize(n); mcity.resize(n); check.resize(k); for (int i = 0; i < m; i++) { int tempi, tempj; scanf("%d %d", &tempi, &tempj); tempi--; tempj--; map[tempi].push_back(tempj); map[tempj].push_back(tempi); } for (int i = 0; i < k; i++) { scanf("%d", &check[i]); } for (int i = 0; i < k; i++) { int q = check[i]; q--; initial(); for (int j = 0; j < n; j++) { for (int k = 0; k < map[j].size(); k++) { int v = map[j][k]; if (q != j && q != v) { unionSet(j, v); } } } set
              
                parentSet; for (int i = 0; i < n; i++) { parentSet.insert(findSet(i)); } cout << parentSet.size() - 1 << endl; } int a; cin >> a; return 0;}