[Atcoder] D - Friends (C++)

Problem

Problem Statement

There are NN persons called Person 11 through Person NN.

You are given MM facts that "Person AiAi and Person BiBi are friends." The same fact may be given multiple times.

If XX and YY are friends, and YY and ZZ are friends, then XX and ZZ are also friends. There is no friendship that cannot be derived from the MM given facts.

Takahashi the evil wants to divide the NN 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?

Constraints

• 2≤N≤2×1052≤N≤2×105
• 0≤M≤2×1050≤M≤2×105
• 1≤Ai, Bi≤N1≤Ai, Bi≤N
• Ai≠Bi

How to solve

- 정보

N: 사람 수

M: 연결 정보 Facts 수

 

사람수 N과, M개의 연결 정보가 주어진다. 

 

- 구하는 것?

예를들어, 

A-B 연결 되어있으면, A-B는 친구이다.

B-C 연결 되어있으면, B-C는 친구이다. 

따라서, A-B-C는 같은 그룹에 속한다. 

 

서로 모르는 사람이 되도록 새로운 그룹을 만들때, 

만들어야하는 그룹 수를 구하는 문제이다.

 

- 예시

Sample Input 1

    5 3

    1 2

    3 4

    5 1

위 경우 아래와 같이 그릴 수 있다. 

1, 2, 5 가 서로 친구이고,

3, 4 가 서로 친구이다. 

이 경우 최대 그룹 수는 1, 2, 5를 찢어서 새로운 그룹을 만드는 가지 수 3이된다. 

 

- 풀이 

DSU를 활용하여 구한다!

연결 정보를 이용하여 연결된 번호를 같은 그룹으로 묶고,

그룹의 최대 원소 수를 return 한다. 

 

**주의 사항**

dsu 초기화 주의!

N번째 사람까지이기 때문에 d(N+1)로 초기화해야한다. 

Solution(c++)

#include <bits/stdc++.h>
#include <atcoder/dsu>

using namespace std;
using namespace atcoder;

int main(){
	int N, M;
	int max_val = 0;
	cin >> N >> M;
	dsu d(N+1);
	
	for(int i=0; i<M; i++){
		int u, v;
		cin >> u >> v;
		d.merge(u, v);
	}
	for(int i=0; i<=N; i++){
		max_val = max(max_val, d.size(i));
	}
	cout << max_val << endl;
	return 0;
}

Test Result

Submission #19416128 - AtCoder Beginner Contest 177

Submission #19416128 - AtCoder Beginner Contest 177