HihoCoder#1066 무간도 병집
6113 단어 code
및 조회 세트 + 경로 압축
데이터량이 많지 않아 등급을 올리는 최적화가 없다
코드:
1 #include <iostream>
2 #include <map>
3 #include <cstring>
4
5 using namespace std;
6
7 #define SIZE 100010
8
9 int disjoin[SIZE];
10 map<string, int> a2i;
11
12 int find(int a) {
13 if (!disjoin[a] || disjoin[a] == a)
14 disjoin[a] = a;
15 else
16 disjoin[a] = find(disjoin[a]);
17 return disjoin[a];
18 }
19
20 void merge(int a, int b) {
21 disjoin[find(a)] = find(b);
22 }
23
24 bool check(int a, int b) {
25 return find(a) == find(b);
26 }
27
28 int main() {
29 int N;
30 int op;
31 string a, b;
32 int ai, bi;
33 int num = 0;
34
35 memset(disjoin, 0, sizeof(int) * SIZE);
36 cin >> N;
37 while (N--) {
38 cin >> op >> a >> b;
39 ai = a2i[a];
40 bi = a2i[b];
41 if (!a2i[a])
42 ai = a2i[a] = ++num;
43 if (!a2i[b])
44 bi = a2i[b] = ++num;
45
46 if (op == 0)
47 merge(ai, bi);
48 else
49 cout << (check(ai, bi) ? "yes" : "no") << endl;
50 }
51 return 0;
52 }
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
소스 코드가 포함된 Python 프로젝트텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.