cogs 259 를 예 로 들 면

제목 링크:http://cogs.pro:8081/cogs/problem/problem.php?pid=pySmxSVgP
[문제 설명]
    아마 너 는 너의 어떤 친구 가 너의 친척 이라는 것 을 모 를 것 이다.그 는 아마 너의 증조부 의 외할아버지 의 사위 의 조카 의 사촌 누나 의 손자 일 것 이다.온전한 가 보 를 얻 을 수 있다 면 두 사람 이 친척 인지 아 닌 지 를 판단 하 는 것 은 가능 할 것 이다. 그러나 두 사람의 최근 공공 조상 이 그들 과 몇 대 를 떨어져 가 보 를 방대 하 게 만 들 었 다 면 친척 관 계 를 검증 하 는 것 은 인력 이 미 칠 수 있 는 일이 아니다.이런 상황 에서 가장 좋 은 도 우 미 는 컴퓨터 다.
    문 제 를 간소화 하기 위해 서 는 Xuebin 과 Grant 가 친척 이 고 Grant 와 Tension 이 친척 이라는 등 친척 관계 에 대한 정 보 를 얻 을 수 있 습 니 다. 이 정보 에서 xuebin 과 Tension 은 친척 입 니 다.친척 관계 에 대한 질문 에 가장 빠 른 속도 로 답 을 주 는 프로그램 을 써 주세요.
[형식 입력]
    입력 은 두 부분 으로 구성 되 어 있 습 니 다:
1 부 는 N, M 으로 시작한다.N 은 문제 와 관련 된 사람의 개수 (1 ＜ N ＜ 20000) 이다.이들 의 번 호 는 1, 2, 3,..., N 이다.아래 에 M 행 (1 ＜ M ＜ 1000000) 이 있 고 각 행 에 두 개의 수 ai, bi 가 있 으 며 이미 ai 와 bi 가 친척 임 을 나타 낸다.
2 부 는 Q 로 시작한다.아래 Q 행 은 Q 개 문의 (1 ＜ Q ＜ 1000000) 가 있 으 며, 각 행위 ci, di 는 ci 와 di 가 친척 인지 여 부 를 묻 는 것 을 나타 낸다.
[출력 형식]
출력 에 몇 줄 이 있 습 니까?
모든 질문 에 ci, di, ci 와 di 가 친척 이면 Yes 를 출력 합 니 다. 그렇지 않 으 면 No 를 출력 합 니 다.
[입 출력 사례]
입력 파일
10 7
2 4
5 7
1 3
8 9
1 2
5 6
2 3
3
3 4
7 10
8 9
출력 파일
Yes
No
Yes
그리고 집합 을 찾 습 니 다. 그리고 집합 을 찾 는 것 은 효율 적 인 분류 알고리즘 입 니 다. 제목 에 뚜렷 한 분류 의미 가 있 을 때 사용 하고 집합 을 찾 아 같은 요소 의 특징 을 추출 하여 분류 하고 찾 을 수 있 습 니 다.
STEP 1: 각 단 위 를 하나의 집합 으로 한다.
두 번 째 단계: 두 요 소 를 찾 습 니 다. 집합 이 다 르 지만 같은 특징 이 있 으 면 하나의 집합 으로 합 칩 니 다.
세 번 째 단계: 수요 에 따라 대응 하 는 집합 요 소 를 찾 습 니 다.
최적화: 경로 압축
나무 뿌리 왼쪽 아들 의 아들 과 나무 뿌리 오른쪽 아들 의 아들 은 집합 으로 두 손 자 를 모두 나무 뿌리 에 연결 시 켜 체인 구 조 를 형성 하 는 것 을 방지 하고 한 층 한 층 씩 찾 아 시간 복잡 도 를 높 일 수 있다 는 것 을 알 수 있다.
코드:

 1 #define _CRT_SECURE_NO_WARNINGS
 2 #include 
 3 #include 
 4 #define MAXN 1000100
 5 using namespace std;
 6  
 7 int N, M, pre[MAXN] = { 0 }, Q;
 8 int ai, bi;
 9  
10 int find(int x)
11 {
12     if (x == pre[x])
13         return x;
14     return pre[x] = find(pre[x]); //    
15 }
16  
17 void Union(int x, int y)
18 {
19     int xPre = find(x);
20     int yPre = find(y);
21     if (xPre != yPre)
22         pre[y] = xPre;
23 }
24  
25 void preWork()
26 {
27     for (int i = 1; i <= N; i++)
28         pre[i] = i;
29 }
30  
31 int main()
32 {
33     freopen("relations.in", "r", stdin);
34     freopen("relations.out", "w", stdout);
35     scanf("%d%d", &N, &M);
36     preWork();
37  
38     while (M--)
39     {
40         scanf("%d %d", &ai, &bi);
41         Union(ai, bi);
42     }
43     scanf("%d", &Q);
44     while (Q--)
45     {
46         scanf("%d %d", &ai, &bi);
47         int aPre = find(ai);
48         int bPre = find(bi);
49         if (aPre != bPre)
50             printf("No
");
51         else
52             printf("Yes
");
53     }
54     return 0;
55 }