AtCoder题解—— AtCoder Beginner Contest 177 —— D - Friends

题目相关

题目链接

AtCoder Beginner Contest 177 D 题，https://atcoder.jp/contests/abc177/tasks/abc177_d。

Problem Statement

There are N persons called Person 1 through Person N. You are given M facts that "Person Ai and Person Bi are friends." The same fact may be given multiple times.

If X and Y are friends, and Y and Z are friends, then X and Z are also friends. There is no friendship that cannot be derived from the M given facts.

Takahashi the evil wants to divide the N persons into some number of groups so that every person has no friend in his/her group. At least how many groups does he need to make?

Input

Input is given from Standard Input in the following format:

N M
A1 B1
.
.
.
AM BM
           

Output

Print the answer.

Samples1

Sample Input 1

5 3
1 2
3 4
5 1
           

Sample Output 1

3
           

Explaination

Dividing them into three groups such as {1,3}, {2,4}, and {5} achieves the goal.

Samples2

Sample Input 2

4 10
1 2
2 1
1 2
2 1
1 2
1 3
1 4
2 3
2 4
3 4
           

Sample Output 2

4
           

Samples3

Sample Input 3

10 4
3 1
4 1
5 9
2 6
           

Sample Output 3

3
           

Constraints

• 2≤N≤2×10^5
• 0≤M≤2×10^5
• 1≤Ai,Bi≤N
• Ai≠Bi

题解报告

题目翻译

给 N 个人，编号从 1 到 N。再给 M 个关系，即 “ Ai 和 Bi，表示 Ai 和 Bi 是朋友”。如果 X 和 Y 是朋友，Y 和 Z 是朋友，那么 X 和 Z 也是朋友。

现在高桥向将这 N 个人进行分组，要求组里的人互相都不是朋友。问最少需要几个组可以满足。

样例数据分析

样例数据 1

根据样例数据 1，我们可以绘制出如下图所示的朋友关系：

如上图所示，1、2 和 5 是朋友关系，3 和 4 是朋友关系。第一个集合中有 3 个元素，第二个集合中有 2 个元素。要完成要求，至少需要 3 个分组。

我们可以从拿出 {1、3} 分为一组；再拿出 {2、4} 分为一组；最后的 {5} 单独分为一组，就可以满足条件，而且没有比这个更少的分组。

样例数据 2

根据样例数据 2，我们可以绘制出如下图所示的朋友关系：

如上图所示，1、2、3 和 4 是朋友关系。第一个集合中有 4 个元素。要完成要求，至少需要 4 个分组。

我们可以从拿出 {1} 分为一组；再拿出 {2} 分为一组；再拿出 {3} 分为一组；最后的 {4} 单独分为一组，就可以满足条件，而且没有比这个更少的分组。

样例数据 3

根据样例数据 3，我们可以绘制出如下图所示的朋友关系：

如上图所示，1、3 和 4 是朋友关系，2 和 6 是朋友关系，5 和 9 是朋友关系，7 是朋友关系，8 是朋友关系，10 是朋友关系。第一个集合中有 3 个元素，第二个集合有 2 个元素，第三个集合有 2 个元素，第四个集合有 1 个元素，第五个集合有 1 个元素，第六个集合有 1 个元素。要完成要求，至少需要 3 个分组。

那么我们可以从拿出 {1、2、5、7、8、10} 分为一组；再拿出 {3、6、9} 分为一组；最后的 {4} 单独分为一组，就可以满足条件，而且没有比这个更少的分组。

题目分析

从上面的数据分析中，我们可以看出，本题属于并查集范畴。根据上面的样例数据分析，我们可以设计出如下的算法：

1、读取数据。

2、建立集合关系。

3、遍历数据，获取最大的集合元素个数。

AC 参考代码

//https://atcoder.jp/contests/abc177/tasks/abc177_d
//D - Friends
/*
人的编号为 1 ~ N，可以使用 vector 表示；N<=2*10^5，因此 int 足够
*/
#include <bits/stdc++.h>

using namespace std;

template <class T>
struct _DISJOINTSET {
    /*
    当_ds[x]<0的时候，说明x的父节点是自己。同时 |_ds[x]| 表示集合内元素数量
    当_ds[x]>0的时候，表示父节点
    */
    vector<T> _ds;//并查集
 
    _DISJOINTSET(T n) {
        _ds = vector<T>(n, -1);
    }
  
    //查找x的父亲
    T find_root(T x) {
        if (_ds[x] < 0) {
            return x;
        }
        return _ds[x] = find_root(_ds[x]);
    }
 
    //建立关系
    bool union_set(T x, T y) {
        x = find_root(x);
        y = find_root(y);
        if (x==y) {
            //两个已经在同一个集合
            return false;
        }
        if (_ds[x]>_ds[y]) {
            //保证不会出现单边增长
            swap(x, y);
        }
        _ds[x] += _ds[y];
        _ds[y] = x;
        return true;
    }
 
    //查找x和y是否在同一个父亲
    bool relation(T x, T y) {
        return find_root(x) == find_root(y);
    }

    //数据 x 所在集合大小
    T size(T x) {
        return -_ds[find_root(x)];
    }
};

int main() {
    int n,m;
    cin>>n>>m;

    _DISJOINTSET<int> uf(n);
    for (int i=0; i<m; i++) {
        int a,b;
        cin>>a>>b;
        uf.union_set(a-1, b-1);
    }

    //find the maximum friends-set
    int ans=0;
    for (int i=0; i<n; i++) {
        ans = max(ans, uf.size(i));
    }

    cout<<ans<<"\n";
    
    return 0;
}
           

时间复杂度

O(N)。