레야몬

1. 문제 N개의 선분들이 2차원 평면상에 주어져 있다. 두 선분이 서로 만나는 경우에 두 선분은 같은 그룹에 속했다고 하며 그룹의 크기는 그 그룹에 속한 선분의 개수로 정의한다. 이 N개의 선분들은 몇 개의 그룹으로 되어있을까? 또, 가장 큰 그룹에 속하는 선분의 개수는 몇 개인가? - 1 - $N(1\le N\le 3,000)$ - N개의 줄 - 선분의 양 끝점의 좌표 $\left|x_i\right|,\left|y_i\right|\le 5,000$ - 1 - 그룹의 수 - 2 - 가장 크기가 큰 그룹에 속한 선분의 개수 2. 재정의 선분 그룹 개수와 그 크기 구하기 3. 해결 방법 N*N = 9,000,000으로 CCW를 이용해 선분 교차를 모두 파악하고 이를 union..

1. 문제 두 사람의 친구 네트워크에 몇 명 있는지 구하는 프로그램을 작성하시오. - 1 - 테스트 케이스의 개수 $T(1\le T\le 100,000)$ - F개의 줄 - 친구 관계가 생긴 순서대로 주어짐. 친구 관계는 두 사용자의 아이디로 이루어져 있으며 이는 알파벳 대문자 또는 소문자로만 이루어진 길이 20 이하의 문자열이다. 친구 관계가 생길 때마다 두 사람의 친구 네트워크에 몇 명이 있는지 구하시오. 2. 재정의 집합의 원소 개수 구하기 3. 해결 방법 unordered-map에 헤시를 써서~~ 4. 실수한 점, 개선할 점 MAX_F가 아니라 MAX_F*2개 만큼 배열을 잡아야 한다. 그 이유는 F개의 친구 관계가 나오므로 최대 친구의 수는 2*F이기 때문이다. #include #in..

1. 문제 초기에 {0}, {1}, ..., {n}이 각각 n+1개의 집합을 이루고 있다. 여기에 합집합 연산과 두 원소가 같은 집합에 있는지 확인하는 연산을 수행하려 한다. - 1 - $n,m(1\le n\le 1,000,000,1\le m\le 100,000)$ m은 입력으로 주어지는 연산의 개수 - m개의 줄 - 각각의 연산 0 a b: 합집합 a에 있는 집합과 b가 있는 집합 합치기 1 a b: 두 원소가 같은 집합에 포함되어 있는지 확인 $0\le a,b\le n$ 1로 시작하는 입력에 대해 YES/NO로 결과를 출력 2. 재정의 집합 연산 3. 해결 방법 트리를 이용한 union-find 수행 4. 실수한 점, 개선할 점 rank랑 union은 이미 표준 라이..