EOJ 1837小强的烦恼
思路
使用带权并查集处理这个题目，根据敌人的敌人是朋友的原则，xy的边权为偶数，则xy是朋友，否则是敌人。如果xy不在同一个并查集里面，则暂时不确定。
code
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 10;
int fa[MAXN];
int edge[MAXN];
inline int find(int x)
{
if(x == fa[x]) return x;
int tf = fa[x];
fa[x] = find(fa[x]);
edge[x] = (edge[x] + edge[tf]) % 2;
return fa[x];
}
inline void merge(int x, int y)
{
if(x == y) return;
edge[x] = edge[y] + 1;
x = find(x);
y = find(y);
fa[x] = y;
}
int n, m;
inline void sov()
{
cin >> n >> m;
for(int i = 1; i <= n; ++i)
fa[i] = i;
for(int i = 1; i <= n; ++i)
edge[i] = 0;
while(m--)
{
char c;
int x, y;
cin >> c >> x >> y;
if(c == 'A')
{
merge(x, y);
}
else if(c == 'Q')
{
int nx = find(x);
int ny = find(y);
if(nx != ny)
{
cout << "Not sure yet.\n";
}
else
{
int d = edge[x] + edge[y];
// cerr << nx << " " << edge[x] << " " << edge[y] << endl;
if(d % 2 == 0)
{
cout << "In the same gang.\n";
}
else
{
cout << "In different gangs.\n";
}
}
}
}
}
int main()
{
int t;
cin >> t;
while(t--) sov();
}