문제
양방향 단순 그래프란 간선이 양방향으로 이어져 있으며, 중복 간선이 없는 그래프를 뜻한다.
양방향 단순 그래프 G에 대하여, 정점들의 부분 집합 V를 V의 어떤 두 원소도 간선으로 연결되어 있지 않다면 V를 '독립 집합'이라고 하자.
주어진 무방향 단순 그래프 G에 대하여, G의 독립 집합 중 크기가 최대인 것의 크기를 구하여라.
입력
첫 번째 줄에 정점의 개수인 N과 간선의 개수인 M이 공백으로 구분되어 주어진다.
두 번째 줄부터 M개의 줄에, 각 간선을 나타내는 U, V가 공백으로 구분되어 주어진다. 이는 U와 V를 잇는 간선이 존재한다는 뜻이다.
- 1 ≤ N ≤ 100
- N - 1 ≤ M ≤ N + 15
- 1 ≤ U, V <= N
- U != V
출력
첫 번째 줄에 주어진 그래프의 독립 집합 중 크기가 최대인 것의 크기를 출력하여라.
예제
4 5
1 2
2 3
3 4
4 1
2 4
2
출처
BAPC 2019 | dennisstar
로그인해야 코드를 작성할 수 있어요.