【題目敘述】http://codeforces.com/edu/course/2/lesson/7/2/practice/contest/289391/problem/I
【解題想法】啟發式合併
#include <iostream>
#include <vector>
using namespace std;
int n, m, p[200005], c[200005], shift;
vector <int> v[200005];
int f(int x){
if (x == p[x]) return x;
return p[x] = f(p[x]);
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++){
p[i] = i;
v[i].push_back(i);
}
for (int i = 1, t, a, b; i <= m; i++){
cin >> t >> a >> b;
a = (a+shift)%n;
if (!a) a = n;
b = (b+shift)%n;
if (!b) b = n;
if (t == 0){
if (f(a) == f(b)) continue;
if (c[a] == c[b]){
a = f(a);
b = f(b);
if (v[a].size() < v[b].size()) swap(a, b);
p[b] = a;
while (v[b].size()){
c[v[b].back()] ^= 1;
v[a].push_back(v[b].back());
v[b].pop_back();
}
}
else{
a = f(a);
b = f(b);
if (v[a].size() < v[b].size()) swap(a, b);
p[b] = a;
while (v[b].size()){
v[a].push_back(v[b].back());
v[b].pop_back();
}
}
}
else{
if (c[a] == c[b]){
cout << "YES\n";
shift++;
}
else cout << "NO\n";
}
}
}