題目連結: https://zerojudge.tw/ShowProblem?problemid=a445
# 內容
我的朋友很少～但是朋友的朋友就是我的朋友！請輸出 P 和 Q 是不是朋友
# 解題思路
就是並查集的運用，詳情請洽這裡
# 程式碼
#include<bits/stdc++.h> | |
using namespace std; | |
int parents[10001], ranks[10001]; | |
int FindParent(int x) { | |
return (parents[x] == -1 ? x : parents[x] = FindParent(parents[x])); | |
} | |
bool Joint(int x, int y) { | |
x = FindParent(x), y = FindParent(y); | |
if (x == y) | |
return false; | |
if (ranks[x] > ranks[y]) | |
ranks[y] += ranks[x], parents[x] = y; | |
else | |
ranks[x] += ranks[y], parents[y] = x; | |
return true; | |
} | |
int main() { | |
cin.sync_with_stdio(false), cin.tie(0); | |
int N, M, Q, x, y; | |
cin >> N >> M >> Q; | |
for (int i = 1; i <= N; i++) | |
parents[i] = -1, ranks[i] = 1; | |
while (M--) | |
cin >> x >> y, Joint(x, y); | |
while (Q--) { | |
cin >> x >> y; | |
if (FindParent(x) == FindParent(y)) | |
cout << ":)\n"; | |
else | |
cout << ":(\n"; | |
} | |
} |
