종교 > 문제은행

본문 바로가기


알고리즘 자료구조2

1863 : 종교

제한시간: 1000 ms    메모리제한: 64 MB
해결횟수: 157 회    시도횟수: 767 회   



오늘날 아주 많은 다른 종교들이 있고 이들 모두를 추적하는 것은 어려운 일이다.
당신이 다니는 학교에서 학생들이 믿고 있는 종교가 총 몇 가지 있는가를 알고자 한다.


학교에는 n (0 < n ≤ 50,000)명의 학생이 있다.
모든 학생에게 자기가 가진 종교가 무엇인지를 물어보는 것은 힘든 일이고 게다가 많은 학생들은 그들의 종교를 나타내는 것을 좋아하지 않는다.


이 문제를 해결하기 위한 한 가지 방법은 같은 종교를 가지는 사람들 끼리 짝을 짓도록 하는 것이다.


쌍의 수는 m ( 0 ≤ m ≤ 100,000 ) 이다. 이 데이터로 당신은 모든 학생들이 어떤 종교를 가지고 있는가는 알지 못하지만 학생들이 최대한 가질 수 있는 종교의 가지 수를 알 수 있다.


모든 학생들이 최대 한 가지 종교를 가지고 있다고 하자.


정수 n , m 이 주어진다. 다음 m 라인은 두 정수 i , j 가 주어진다. i, j 는 i번 학생과 j번 학생이 같은 종교를 가진 학생의 쌍이다(1≤i, j≤n).



종교의 가지 수를 출력한다.


[Copy]
10 9
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
[Copy]
1



HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.