2021秋季《数据结构》_EOJ 1083.小强的烦恼

题目

思路

不得不说这个题干实在是蚌埠住了）
敌人的敌人是朋友
开俩数组，一个记朋友一个记敌人
压缩路径可以大大提高效率

代码

#include<bits/stdc++.h>
using namespace std;int a[100001];
int b[100001];int findFriend(int a[], int x)
{int k = x;while(a[k]!=k)k=a[k];while(x!=k){int j=a[x];a[j]=k;x=j;}return k;
}void newFriend(int a[], int x, int y)
{int f1 = findFriend(a, x);int f2 = findFriend(a, y);a[f1] = f2;
}int main()
{int t; cin >> t;for (int q = 0; q < t; q++){int n, m; cin >> n >> m;for (int i = 1; i <= n; i++){a[i] = i;  // 自己是自己的朋友b[i] = -1;}for (int i = 0; i < m; i++){char sig; int x, y;cin >> sig >> x >> y;if (sig == 'A')  // 扫入敌人{if (b[x] == -1)  // x还没有敌人b[x] = y;else  // x已有敌人{newFriend(a, b[x], y);  // b[x]：x的敌人；y：x的敌人}if (b[y] == -1)b[y] = x;elsenewFriend(a, x, b[y]);}else if (sig == 'Q'){if(x == y)cout << "In the same gang." << endl;else{int f1 = findFriend(a, x);int f2 = findFriend(a, y);if (f1 == f2)cout << "In the same gang." << endl;else if (f1 != f2){if (b[f1] == f2 || b[f2] == f1)cout << "In different gangs." << endl;elsecout << "Not sure yet." << endl;}}}}}return 0;
}