yuzining

用户名：yuzining

访问量：898

签　名：

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

　　自我简介：

TA的其他文章

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

你可能喜欢

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

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

　　作者: yuzining　　　　发表时间：2020-04-26 09:06:19 浏览：484　|　评论：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语言程序设计教程（第三版）课后习题8.9 （C语言代码）

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

C二级辅导-阶乘数列（C语言代码）

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

产生数（C++代码）（大数乘法也是可以避免的么hhhh）

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

评论区

精彩推荐

简洁的代码

Biggest Number （C++代码）回溯法

WU-格式化数据输出（C语言代码）

1009题解

陈教主的三角形（C语言代码）

震宇大神的杀毒软件（C语言代码）

Pascal三角（C语言代码）

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

1197求助

生日日数（C语言代码）

yuzining

TA的其他文章

你可能喜欢

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

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

C二级辅导-阶乘数列 （C语言代码）

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

产生数 （C++代码）（大数乘法也是可以避免的么hhhh）

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

评论区

精彩推荐

简洁的代码

Biggest Number （C++代码）回溯法

WU-格式化数据输出 （C语言代码）

1009题解

陈教主的三角形 （C语言代码）

震宇大神的杀毒软件 （C语言代码）

Pascal三角 （C语言代码）

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

1197求助

生日日数 （C语言代码）

C二级辅导-阶乘数列（C语言代码）

产生数（C++代码）（大数乘法也是可以避免的么hhhh）

　　评论区

WU-格式化数据输出（C语言代码）

陈教主的三角形（C语言代码）

震宇大神的杀毒软件（C语言代码）

Pascal三角（C语言代码）

生日日数（C语言代码）