[洛谷]P1525 [NOIP2010 提高组] 关押罪犯（并查集+图论）

**洛谷 P1525 [NOIP2010 提高组] 关押罪犯**

**题目描述**

在一座城市中，某些地区的罪犯数量较多。现在，我们需要将这些地区分成若干个小区，每个小区内都有足够多的罪犯，以便于我们关押他们。在每个小区内，所有罪犯都是相互认识的，而在不同的小区之间，罪犯们是完全不认识的。

城市中共有 n 个地区。每个地区都有一定数量的罪犯。我们需要将这些地区分成若干个小区，每个小区内都有足够多的罪犯，以便于我们关押他们。在每个小区内，所有罪犯都是相互认识的，而在不同的小区之间，罪犯们是完全不认识的。

**输入输出**

* 输入：n（地区数量）、m（边数）、a[i]（地区i中的罪犯数量）、b[i][j](地区i与地区j之间的联系)
* 输出：最少需要关押的小区数量**解决方案**

###1. 并查集我们首先使用并查集来求出每个地区所在的小区编号。

cpp#include <iostream>
#include <vector>

const int N =100000;
int fa[N];

int find(int x) {
 return x == fa[x] ? x : (fa[x] = find(fa[x]));
}

void merge(int a, int b) {
 fa[find(a)] = find(b);
}

cpp#include <iostream>
#include <vector>

const int N =100000;
int n, m;
std::vector<int> a[N];
bool vis[N];

void dfs(int u) {
 vis[u] = true;
 for (auto v : a[u]) {
 if (!vis[v]) {
 dfs(v);
 }
 }
}

cpp#include <iostream>
#include <vector>

const int N =100000;
int n, m;
std::vector<int> a[N];
bool vis[N];

void dfs(int u) {
 vis[u] = true;
 for (auto v : a[u]) {
 if (!vis[v]) {
 dfs(v);
 }
 }
}

int main() {
 std::cin >> n >> m;
 for (int i =0; i < n; ++i) {
 int x;
 std::cin >> x;
 a[i].push_back(i);
 }

 for (int i =0; i < m; ++i) {
 int u, v;
 std::cin >> u >> v;
 a[u].push_back(v);
 a[v].push_back(u);
 }

 for (int i =0; i < n; ++i) {
 if (!vis[i]) {
 dfs(i);
 }
 }

 int ans =0;
 for (int i =0; i < n; ++i) {
 int x = find(i);
 ans = std::max(ans, a[x].size());
 }

 std::cout << ans << std::endl;

 return0;
}