yuzining

用户名：yuzining

访问量：929

签　名：

等　　级
排　　名	58138
经　　验	235
参赛次数	2
文章发表	1
年　　龄	0
在职情况	学生
学　　校	广州大学
专　　业	软件工程

　　自我简介：

TA的其他文章

肺炎大作战-题解(C++代码)（离散化+并查集）
浏览：493

你可能喜欢

C语言程序设计教程（第三版）课后习题11.5 （Java代码）

【明明的随机数】（C++代码）（C++库中有qsort函数直接快排，不用码排序代码hhh）

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

肺炎大作战-题解(C++代码)（离散化+并查集）

　　作者: yuzining　　　　发表时间：2020-04-26 09:06:19 浏览：493　|　评论：1　

原题链接：肺炎大作战

#### 题意转化

给定无数个点n条边的无向连通图，求这个图的最大的连通分量的大小是多少。

#### Solution

这个题的图里点会有无数个，但是关于所在连通分量大小大于等于2的只与给出的n条边有关。

那么我们先对给出的点进行离散化即可。离散化之后，这个图的点最多只有2n个，然后开一个合适大小的并查集。

对于连边的两个点，将两个点离散化后的点在并查集中merge一下。

最后遍历一遍哪个连通分量的大小最大输出即可。

### Code

```cpp
#include<bits/stdc++.h>
using namespace std;
// 并查集模板
struct Dsu {
  vector<int> anc, size;
  Dsu(int n = 0) : anc(n), size(n, 0) {
    iota(anc.begin(), anc.end(), 0);
  }
  int operator[] (int x) {
    return x == anc[x] ? x : anc[x] = operator[](anc[x]);
  }
  bool operator() (int u, int v) {
    int a = operator[](u), b = operator[](v);
    if (a == b) return false;
    if (size[a] < size[b]) anc[a] = b;
    else anc[b] = a, size[a] += (size[a] == size[b]);
    return true;
  }
};
int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  int n;
  while(cin >> n) {
    if(n == 0) {
      cout << 1 << '\n';
      continue;
    }
    vector<int> lsh, u(n), v(n);
    for(int i = 0; i < n; i++) {
      cin >> u[i] >> v[i];
      lsh.push_back(v[i]);
      lsh.push_back(u[i]);
    }
	// 离散化
    sort(lsh.begin(), lsh.end());
    lsh.erase(unique(lsh.begin(), lsh.end()), lsh.end());
    Dsu o(int(lsh.size())); // 开一个合适大小的并查集
    vector<int> siz(lsh.size(), 0); // 记录每个连通分量
    for(int i = 0; i < n; i++) {
      const int U = lower_bound(lsh.begin(), lsh.end(), u[i]) - lsh.begin();
      const int V = lower_bound(lsh.begin(), lsh.end(), v[i]) - lsh.begin();
      o(U, V); // merge
    }
    for(int i = 0; i < int(lsh.size()); i++) {
      siz[o[i]]++;
    }
    cout << *max_element(siz.begin(), siz.end()) << '\n';
  }
}
```

~~吐槽：居然不能用mathjax~~

0.0分

7 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

　　评论区

yuzining

@wlzhouzhuan

2020-04-26 09:10:09

yuzining

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题11.5 （Java代码）

C语言训练-亲密数（C++代码）

【明明的随机数】（C++代码）（C++库中有qsort函数直接快排，不用码排序代码hhh）

C二级辅导-求偶数和（C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

肺炎大作战-题解(C++代码)（离散化+并查集）

评论区

精彩推荐

WU-判定字符位置（C++代码）

C语言程序设计教程（第三版）课后习题6.2 （C语言代码）

【绝对值排序】（C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

1124题解

矩形面积交（C++代码）

C语言程序设计教程（第三版）课后习题10.3 （C语言代码）

拆分位数（C语言代码）

C二级辅导-计负均正（C语言代码）

P1044 （C++代码）

yuzining

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题11.5 （Java代码）

C语言训练-亲密数 （C++代码）

【明明的随机数】 （C++代码）（C++库中有qsort函数直接快排，不用码排序代码hhh）

C二级辅导-求偶数和 （C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

肺炎大作战-题解(C++代码)（离散化+并查集）

评论区

精彩推荐

WU-判定字符位置 （C++代码）

C语言程序设计教程（第三版）课后习题6.2 （C语言代码）

【绝对值排序】 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

1124题解

矩形面积交 （C++代码）

C语言程序设计教程（第三版）课后习题10.3 （C语言代码）

拆分位数 （C语言代码）

C二级辅导-计负均正 （C语言代码）

P1044 （C++代码）

C语言训练-亲密数（C++代码）

【明明的随机数】（C++代码）（C++库中有qsort函数直接快排，不用码排序代码hhh）

C二级辅导-求偶数和（C语言代码）

　　评论区

WU-判定字符位置（C++代码）

【绝对值排序】（C语言代码）

矩形面积交（C++代码）

拆分位数（C语言代码）

C二级辅导-计负均正（C语言代码）