審題：

本題需要我們通過解析所有人之間的關系，從而判斷出朋友團體的總個數并輸出

思路：

方法一：擴展域并查集

由于這里涉及對朋友/敵人等關系集合的頻繁操作，所以我們需要使用并查集來操作，但是普通的并查集只有一種集合域，也就是只能維護一種關系。這里有兩種關系存在，常規并查集已經無法滿足要求，所以我們需要使用擴展域并查集

補充：擴展域并查集

相比于普通并查集來說，這種并查集可以維護更多的關系，具體的實現邏輯如下

1.將fa數組的集合域分為朋友域和敵人域

朋友域為1~n，敵人域為1+n~n+n

2.對于x元素來說，和x在同一個集合的是朋友，和x+n在同一個集合的是敵人

講解操作過程：

假設現在人數n為3,1和2是敵人，2和3是敵人。

接下來我們按照擴展域并查集的邏輯進行模擬操作

由于1和2是敵人，所以我們將1和2的敵人域連起來，將2和1的敵人域連起來，同理后面2和3也近似操作

按照題意，敵人的敵人就是朋友，所以1和3應該是朋友。而我們看到經過前面的操作，1和3處于同一個集合，滿足題意，方法成立

解題：
?

#include<iostream>
using namespace std;
const int N = 1010;
int n, m;
int fa[N * 2];
int find(int x)
{return fa[x] == x ? x : fa[x] = find(fa[x]);
}
void un(int x, int y)//讓朋友域當根節點
{fa[find(x)] = find(y);
}int main()
{cin >> n >> m;//初始化擴展并查集for (int i = 1; i <= 2 * n; i++){fa[i] = i;}//建立關系for (int i = 1; i <= m; i++){char x;int y, z;cin >> x >> y >> z;if (x == 'E')//敵人關系{un(z + n, y);un(y + n, z);}else//朋友關系{un(y, z);}}//查詢團伙數int ret = 0;for (int i = 1; i <= n; i++){if (fa[i] == i) ret++;}cout << ret << endl;return 0;
}

注意：

1.題目中只說了兩個條件：一個是敵人的敵人是朋友，另一個是朋友的朋友是朋友。

但是沒有說朋友的敵人是不是敵人，敵人的朋友是不是敵人，所以我們不需要進行特別的其他操作

2.由于實際上存在的人數是n，敵人域是我們自己構建的，所以我們最后統計團伙的時候不能統計到敵人域，只需要統計前n個即可

3.由于我們統計的是朋友域，所以我們的根節點一定要是朋友域的節點，否則就無法統計到了，在傳參給un函數的時候要注意順序

P1892 [BalticOI 2003] 團伙 - 洛谷