2.The Suspects 模版题
4.How Many Answers Are Wrong 带权并查集
5.食物链 带权并查集 / 种类并查集
7.Supermarket 贪心+并查集优化
8.Parity game 离散化 + 带权并查集
9.Navigation Nightmare 离线+ 带权并查集 + xy双方向
10.A Bug's Life 带权并查集模版题
11.Rochambeau 枚举+ 带权并查集 + 思维
12.Connections in Galaxy War 思维 + 点带权倒序并查集
13.小希的迷宫 模版题
14.Is It A Tree? 模版题
建议做题顺序：
模版题：3、2、1、13/14
带权并查集：10、4、5、8、9、11
“点带权”并查集：12
优化查询：7
1.Wireless Network
题目描述：
n个点，最开始都是死节点，两种操作：
- "O p"，即修理x号点
- "S p q" , 判断 p 和 q 能否相连
思路：
就是一个板子题，就是多了一步将坐标转换成距离的过程
/*
Work by: Chelsea
Problem: 不知名屑题
Knowledge: 垃圾算法
Time: O(能过)
*/
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
//#include<unordered_map>
using namespace std;
#define endl '\n'
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define mod 1000000007
#define y1 y114514
#define sz(s) (int)(s).size()
#define sd(n) scanf("%d",&n)
#define sl(n) scanf("%lld",&n)
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define io ios::sync_with_stdio(false);
#define mem(a,b) memset((a),(b),sizeof(a))
#define m_p(a,b) make_pair(a, b)
//#define int long long
typedef long long ll;
typedef pair <int,int> pii;
typedef unsigned long long ull;
//不开longlong见祖宗!
//不改范围见祖宗!!!
#define MAX 300000 + 50
int n, m, k;
int x, y, z;
int a, b, c;
string s, t;
char op;
int fa[MAX];
pair<int, int>tr[1005];
inline void init(){
for(int i = 1; i <= n; ++i)fa[i] = i;
}
inline int getfa(int x){
return x == fa[x] ? x : (fa[x] = getfa(fa[x]));
}
inline void emerge(int x, int y){
fa[getfa(x)] = getfa(y);
}
bool getdis(int x, int y){
a = tr[x].first - tr[y].first;
b = tr[x].second - tr[y].second;
return a * a + b * b <= m * m;
}
bool vis[MAX];
void work(){
cin>>n>>m;
init();
for(int i = 1; i <= n; ++i){
cin>>tr[i].first>>tr[i].second;
}
while (cin>>op) {
if(op == 'O'){
cin>>x;
vis[x] = 1;
for(int y = 1; y <= n; ++y){
if(getdis(x, y) && vis[y]){
emerge(x, y);
}
}
}
else{
cin>>x>>y;
if(getfa(x) == getfa(y))cout<<"SUCCESS\n";
else cout<<"FAIL\n";
}
}
}
int main(){
io;
// int tt;cin>>tt;
// for(int _t = 1; _t <= tt; ++_t){
// printf("Case #%d: ", _t);
work();
// }
return 0;
}
2.The Suspects
题目描述：
n个人，编号从0到1，m个小团体，小团体的人都是朋友关系，朋友的朋友是朋友，现在0号感染了病毒，问0号的朋友有多少个
思路：
板子题，在emerge的时候以小的为根结点就行，最后计算getfa(x) = 0的数量即可
/*
Work by: Chelsea
Problem: 不知名屑题
Knowledge: 垃圾算法
Time: O(能过)
*/
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
//#include<unordered_map>
using namespace std;
#define endl '\n'
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define mod 1000000007
#define y1 y114514
#define sz(s) (int)(s).size()
#define sd(n) scanf("%d",&n)
#define sl(n) scanf("%lld",&n)
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define io ios::sync_with_stdio(false);
#define mem(a,b) memset((a),(b),sizeof(a))
#define m_p(a,b) make_pair(a, b)
//#define int long long
typedef long long ll;
typedef pair <int,int> pii;
typedef unsigned long long ull;
//不开longlong见祖宗!
//不改范围见祖宗!!!
#define MAX 300000 + 50
int n, m, k;
int x, y, z;
int a, b, c;
string s, t;
char op;
int fa[MAX];
int getfa(int x){
return x == fa[x] ? x : fa[x] = getfa(fa[x]);
}
inline void emerge(int x, int y){
int xx = getfa(x);
int yy = getfa(y);
if(xx < yy)fa[yy] = xx;
else fa[xx] = yy;
}
void work(){
while (cin>>n>>m && (n + m)) {
rep(i, 0, n - 1)fa[i] = i;
while (m--) {
cin>>k>>x;
--k;
while (k--) {
cin>>y;
emerge(x, y);
}
}
int ans = 0;
rep(i, 0, n - 1){
if(getfa(i) == 0)++ans;
}
cout<<ans<<endl;
}
}
int main(){
// io;
// int tt;cin>>tt;
// for(int _t = 1; _t <= tt; ++_t){
// printf("Case #%d: ", _t);
work();
// }
return 0;
}
3.How Many Tables
题目描述：
n个人，m个关系，问不同的组的数量
思路：
板子题，合并完判断fa[x] = x的数量即可
/*
Work by: Chelsea
Problem: 不知名屑题
Knowledge: 垃圾算法
Time: O(能过)
*/
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
//#include<unordered_map>
using namespace std;
#define endl '\n'
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define mod 1000000007
#define y1 y114514
#define sz(s) (int)(s).size()
#define sd(n) scanf("%d",&n)
#define sl(n) scanf("%lld",&n)
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define io ios::sync_with_stdio(false);
#define mem(a,b) memset((a),(b),sizeof(a))
#define m_p(a,b) make_pair(a, b)
//#define int long long
typedef long long ll;
typedef pair <int,int> pii;
typedef unsigned long long ull;
//不开longlong见祖宗!
//不改范围见祖宗!!!
#define MAX 300000 + 50
int n, m, k;
int x, y, z;
int a, b, c;
string s, t;
char op;
int fa[MAX];
int getfa(int x){
return x == fa[x] ? x : fa[x] = getfa(fa[x]);
}
inline void emerge(int x, int y){
fa[getfa(x)] = getfa(y);
}
void work(){
cin>>n>>m;
rep(i, 1, n)fa[i] = i;
rep(i, 1, m){
cin>>x>>y;
emerge(x, y);
}
int ans = 0;
rep(i, 1, n){
if(fa[i] == i)++ans;
}
cout<<ans<<endl;
}
int main(){
io;
int tt;cin>>tt;
for(int _t = 1; _t <= tt; ++_t){
// printf("Case #%d: ", _t);
work();
}
return 0;
}
4.How Many Answers Are Wrong
题目描述：
区间大小为[1, n]，m个已知条件，表$\sum_{l}^{r}{a[i]}$，问有多少个错误的已知条件
思路：
很经典的带权并查集
val[x] 表示x的父节点到x的距离
查询的过程写成这样：
int getfa(int x){ if(x != fa[x]){ int ff = fa[x]; fa[x] = getfa(fa[x]);//先找根节点 val[x] += val[ff];//再更新距离 } return fa[x]; }由于 val[x] 表示的是x到父亲节点的距离，而不是到根节点的距离，所以我们路径压缩的过程会改变父节点，而 x 到根节点的过程是 x 到 父节点 + x的父节点到 x 的父节点的父节点……,所以要先找到根节点，找完以后从后往前搞，先x更新的是x的父节点的父节点的父节点……再是x的父节点，最后是x的val，
合并的过程要写成这个样子：
void emerge(int x, int y, int z){ int xx = getfa(x); int yy = getfa(y); if(xx == yy){ if(val[x] - val[y] != z)++ans; } else{ fa[xx] = yy; val[xx] = val[y] + z - val[x]; } }如果 l 和 r 在一个集合，就判断两个点的距离是不是和输入的一样
如果不在一个集合，就合并一下，更新一下val值
还有就是为了保证连续性，我们搞成左开右闭的区间，即(l-1, r]，这样就能连起来了
/*
Work by: Chelsea
Problem: 不知名屑题
Knowledge: 垃圾算法
Time: O(能过)
*/
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
//#include<unordered_map>
using namespace std;
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("Ofast")
#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")
#define eps 1e-8
#define endl '\n'
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define NMAX 1000 + 50
#define ls p<<1
#define rs p<<1|1
//#define mod 1000000007
#define y1 y114514
#define lowbit(x) (x & (-x))
#define sz(s) (int)(s).size()
#define sd(n) scanf("%d",&n)
#define sl(n) scanf("%lld",&n)
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define sll(n,m) scanf("%lld %lld",&n,&m)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n",n, m)
#define sddd(n,m,z) scanf("%d %d %d",&n,&m,&z)
#define slll(n,m,z) scanf("%lld %lld %lld",&n,&m,&z)
#define io ios::sync_with_stdio(false);
#define mem(a,b) memset((a),(b),sizeof(a))
#define m_p(a,b) make_pair(a, b)
//#define int long long
typedef long long ll;
typedef pair <int,int> pii;
typedef unsigned long long ull;
//不开longlong见祖宗!
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}
//不改范围见祖宗!!!
#define MAX 300000 + 50
int n, m, k, op;
int x, y, z;
int a, b, c;
string s, t;
int ans;
int fa[MAX];
int val[MAX];
int getfa(int x){
if(x == fa[x])return x;
int ff = fa[x];
fa[x] = getfa(fa[x]);
val[x] += val[ff];
return fa[x];
}
inline void emerge(int x, int y, int z){
int xx = getfa(x);
int yy = getfa(y);
if(xx == yy){
if(val[y] - val[x] != z){
++ans;
}
}
else {
fa[yy] = xx;
val[yy] = val[x] + z - val[y];
}
}
void work(){
while (cin>>n>>m) {
mem(val, 0);
ans = 0;
rep(i, 0, n)fa[i] = i;
rep(i, 1, m){
cin>>x>>y>>z;
--x;
emerge(x, y, z);
}
cout<<ans<<endl;
}
}
int main(){
io;
// int tt;cin>>tt;
// for(int _t = 1; _t <= tt; ++_t){
// printf("Case #%d: ", _t);
work();
// }
return 0;
}
5.食物链
题目描述：
动物王国中有三类动物A,B,C，这三类动物的食物链构成了有趣的环形。A吃B， B吃C，C吃A。
现有N个动物，以1－N编号。每个动物都是A,B,C中的一种，但是我们并不知道它到底是哪一种。
有人用两种说法对这N个动物所构成的食物链关系进行描述：
第一种说法是"1 X Y"，表示X和Y是同类。
第二种说法是"2 X Y"，表示X吃Y。
此人对N个动物，用上述两种说法，一句接一句地说出K句话，这K句话有的是真的，有的是假的。当一句话满足下列三条之一时，这句话就是假话，否则就是真话。
1） 当前的话与前面的某些真的话冲突，就是假话；
2） 当前的话中X或Y比N大，就是假话；
3） 当前的话表示X吃X，就是假话。
思路1：
带权并查集
val[x] = 0 表示x和x的父节点是同种关系
val[x] = 1表示x吃x节点
val[x] = 2表示x被x的父节点吃
我们简单分析一下
假设 x 吃 y ，y 吃 z，根据题意z应该吃x，也就是当x的父节点是z的时候，val[x]=1，x->y->z, x->z为4，对3取模后刚好等于1，符合题意，所以我们只需要用对距离取模来表示关系即可
int getfa(int x){ if(x == fa[x])return x; int ff = fa[x]; fa[x] = getfa(fa[x]); val[x] = (val[x] + val[ff]) % 3; return fa[x]; }void emerge(int x, int y, int z){ int xx = getfa(x); int yy = getfa(y); if(xx == yy){ if(val[x] != (val[y] + z) % 3)++ans; } else{ fa[xx] = yy; val[xx] = (z + val[y] - val[x] + 3) % 3; } }
/*
Work by: Chelsea
Problem: 不知名屑题
Knowledge: 垃圾算法
Time: O(能过)
*/
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
#include<unordered_map>
using namespace std;
#define eps 1e-8
#define endl '\n'
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define NMAX 1000 + 50
#define ls p<<1
#define rs p<<1|1
#define mod 1000000007
#define lowbit(x) (x & (-x))
#define sz(s) (int)(s).size()
#define sd(n) scanf("%d",&n)
#define sl(n) scanf("%lld",&n)
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define sll(n,m) scanf("%lld %lld",&n,&m)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n",n, m)
#define sddd(n,m,z) scanf("%d %d %d",&n,&m,&z)
#define slll(n,m,z) scanf("%lld %lld %lld",&n,&m,&z)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
#define m_p(a,b) make_pair(a, b)
//#define int long long
typedef long long ll;
typedef pair <int,int> pii;
typedef unsigned long long ull;
//不开longlong见祖宗!
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}
//不改范围见祖宗!!!
#define MAX 300000 + 50
int n, m, k, op;
int x, y, z;
ll a, b, c;
string s, t;
int fa[MAX];
int val[MAX];
int ans;
int getfa(int x){
if(x == fa[x])return x;
int ff = fa[x];
fa[x] = getfa(fa[x]);
val[x] = (val[x] + val[ff]) % 3;
return fa[x];
}
void emerge(int x, int y, int z){
int xx = getfa(x);
int yy = getfa(y);
if(xx == yy){
if(val[x] != (val[y] + z) % 3)++ans;
}
else{
fa[xx] = yy;
val[xx] = (z + val[y] - val[x] + 3) % 3;
}
}
void work(){
cin>>n>>m;
rep(i, 1, n)fa[i] = i;
rep(i, 1, m){
cin>>z>>x>>y;
if(x > n || y > n || (z == 2 && x == y))++ans;
else emerge(x, y, z - 1);
}
cout<<ans<<endl;
}
int main(){
io;
// int tt;cin>>tt;
// for(int _t = 1; _t <= tt; ++_t){
// printf("Case #%d: ", _t);
work();
// }
return 0;
}
思路2：
由于每个动物只有三种情况，所以说我们可以“枚举”，开三倍的数组，第一层1到n表示他们都是动物A，第二层n+1到2n表示他们都是动物B，第三层2n+1到3n表示他们都是动物C
如果告诉x吃y的时候，就对每种情况进行合并，emerge(x, y + n), emerge(x + n, y + 2 * n),emerge(x + 2 * n, y)，
判断的时候也类似
/*
Work by: Chelsea
Problem: 不知名屑题
Knowledge: 垃圾算法
Time: O(能过)
*/
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
//#include<unordered_map>
using namespace std;
//#pragma GCC optimize("Ofast")
//#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
//#pragma GCC optimize("unroll-loops")
#define eps 1e-8
#define endl '\n'
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define NMAX 1000 + 50
#define ls p<<1
#define rs p<<1|1
#define mod 1000000007
#define lowbit(x) (x & (-x))
#define sz(s) (int)(s).size()
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define sl(n) scanf("%lld",&n)
#define sll(n,m) scanf("%lld %lld",&n,&m)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n",n, m)
#define sddd(n,m,z) scanf("%d %d %d",&n,&m,&z)
#define slll(n,m,z) scanf("%lld %lld %lld",&n,&m,&z)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
#define m_p(a,b) make_pair(a, b)
typedef long long ll;
typedef pair <int,int> pii;
typedef unsigned long long ull;
//不开longlong见祖宗!
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}
//不改范围见祖宗!!!
#define MAX 300000 + 50
int n, m, k, op;
int x, y, z;
int a, b, c;
string s, t;
int fa[MAX];
int getfa(int x){
return x == fa[x] ? x : fa[x] = getfa(fa[x]);
}
inline void emerge(int x, int y){
fa[getfa(x)] = getfa(y);
}
void work(){
cin>>n>>m;
for(int i = 1; i <= 3 * n; ++i)fa[i] = i;
int ans = 0;
for(int i = 1; i <= m; ++i){
cin>>op>>x>>y;
if(x > n || y > n)++ans;
else{
if(op == 1){
if(getfa(x) == getfa(y + n) || getfa(x) == getfa(y + 2 * n)){
++ans;
continue;
}
emerge(x, y);
emerge(x + n, y + n);
emerge(x + 2 * n, y + 2 * n);
}
else{
if(getfa(x) == getfa(y) || getfa(x) == getfa(y + 2 * n)){
++ans;
continue;
}
emerge(x, y + n);
emerge(x + n, y + 2 * n);
emerge(x + 2 * n, y);
}
}
}
cout<<ans<<endl;
}
int main(){
io;
// int tt;cin>>tt;
// for(int _t = 1; _t <= tt; ++_t){
// printf("Case #%d: ", _t);
work();
// }
return 0;
}
7.Supermarket
题目描述：
n个商品，每个商品都有一个截止日期，如果在截止日期之前卖出就能获得他的价值，否则就不能得到他的价值，问如何安排能使得获得的价值最多
思路：
贪心+并查集优化
先买价值大的，从他的截止日期开始往前挑一个最近的没有用过的日期
虽然这个题用直接for循环就能过，不用并查集优化，但是这个并查集优化区间查询第一个符合条件的点的方法很妙
主要思想是合并点，将用过的点合并到下一个点去
for(int i = l; i <= r ;i = getfa(i + 1)){ if(){ //按题意更新 fa[i] = getfa(i + 1);//更新fa数组 break;//因为只更新一个点所以直接break } }
/*
Work by: Chelsea
Problem: 不知名屑题
Knowledge: 垃圾算法
Time: O(能过)
*/
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
//#include<unordered_map>
using namespace std;
//#pragma GCC optimize("Ofast")
//#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
//#pragma GCC optimize("unroll-loops")
#define eps 1e-8
#define endl '\n'
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define NMAX 1000 + 50
#define ls p<<1
#define rs p<<1|1
#define mod 998244353
#define lowbit(x) (x & (-x))
#define sz(s) (int)(s).size()
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define sl(n) scanf("%lld",&n)
#define sll(n,m) scanf("%lld %lld",&n,&m)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n",n, m)
#define sddd(n,m,z) scanf("%d %d %d",&n,&m,&z)
#define slll(n,m,z) scanf("%lld %lld %lld",&n,&m,&z)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
#define m_p(a,b) make_pair(a, b)
typedef long long ll;
typedef pair <int,int> pii;
typedef unsigned long long ull;
//不开longlong见祖宗!
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}
//不改范围见祖宗!!!
#define MAX 300000 + 50
int n, m, k, op;
int x, y, z;
int l, r;
string s, t;
struct ran{
int l, val;
}tr[MAX];
bool cmp(ran a, ran b){
if(a.val != b.val)return a.val > b.val;
else return a.l < b.l;
}
int fa[MAX];
int getfa(int x){
return x == fa[x] ? x : fa[x] = getfa(fa[x]);
}
void work(){
while(cin>>n){
for(int i = 1; i <= 10000; ++i)fa[i] = i;
for(int i = 1; i <= n; ++i)cin>>tr[i].val>>tr[i].l;
sort(tr + 1, tr + 1 + n, cmp);
ll ans = 0;
for(int i = 1; i <= n; ++i){
x = getfa(tr[i].l);
if(x < 1)continue;
ans += tr[i].val;
fa[x] = getfa(x - 1);
}
cout<<ans<<endl;
}
}
int main(){
// io;
// int tt;cin>>tt;
// for(int _t = 1; _t <= tt; ++_t){
// printf("Case #%d: ", _t);
work();
// }
return 0;
}
8.Parity game
题目描述：
长度为n的01串，m个提示，每个提示会告诉你[l, r]中1的个数是奇数还是偶数，问这些提示有没有自相矛盾的时候，如果有，请输出第一个出现矛盾的地方，没有就输出m
思路：
离散化 + 带权并查集，但是不是很好看出来
方法是将这个01串求一个前缀和，这样如果[l,r]有奇数个的1，就说明sum[l]和sum[r]的奇偶性不同，如果有偶数个1，就说明奇偶性相同，而sum[i]只有两种奇偶性，要么是奇数，要么是偶数，所以就可以判断了
和上面的那个食物链就差不多了，两种方法都可以，这里因为就只有两种情况，我们可以不取模，而是用异或
同样的，给l-1，变成(l – 1, r]的左开右闭区间
很坑的是需要离散化
/*
Work by: Chelsea
Problem: 不知名屑题
Knowledge: 垃圾算法
Time: O(能过)
*/
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
//#include<unordered_map>
using namespace std;
//#pragma GCC optimize(2)
//#pragma GCC optimize(3)
//#pragma GCC optimize("inline")
//#pragma GCC optimize("-fgcse-lm")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
//#pragma GCC optimize("unroll-loops")
#define eps 1e-8
#define endl '\n'
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define NMAX 1000 + 50
#define ls p<<1
#define rs p<<1|1
//#define mod 1000000007
#define y1 y114514
#define lowbit(x) (x & (-x))
#define sz(s) (int)(s).size()
#define sd(n) scanf("%d",&n)
#define sl(n) scanf("%lld",&n)
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define sll(n,m) scanf("%lld %lld",&n,&m)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n",n, m)
#define sddd(n,m,z) scanf("%d %d %d",&n,&m,&z)
#define slll(n,m,z) scanf("%lld %lld %lld",&n,&m,&z)
#define io ios::sync_with_stdio(false);
#define mem(a,b) memset((a),(b),sizeof(a))
#define m_p(a,b) make_pair(a, b)
//#define int long long
typedef long long ll;
typedef pair <int,int> pii;
typedef unsigned long long ull;
//不开longlong见祖宗!
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}
//不改范围见祖宗!!!
#define MAX 300000 + 50
int n, m, k, op;
int x, y, z;
int a, b, c;
string s, t;
int ans, tot;
map<int, int>mp;
int fa[MAX];
int val[MAX];
inline int lh(int x){
if(!mp.count(x))mp[x] = ++tot;
return mp[x];
}
int getfa(int x){
if(x == fa[x])return x;
int ff = fa[x];
fa[x] = getfa(fa[x]);
val[x] ^= val[ff];
return fa[x];
}
bool emerge(int x, int y, int z){
int xx = getfa(x);
int yy = getfa(y);
if(xx == yy){
if((val[x] ^ val[y]) != z){
return false;
}
}
else{
fa[yy] = xx;
val[yy] = val[x] ^ val[y] ^ z;
}
return true;
}
void work(){
cin>>n>>m;
for(int i = 0; i <= 100000; ++i)fa[i] = i;
rep(i, 1, m){
cin>>x>>y>>s;
--x;
x = lh(x);y = lh(y);
if(s[0] == 'e')z = 0;
else z = 1;
if(!emerge(x, y, z)){
cout<<i - 1<<endl;
return;
}
}
cout<<m<<endl;
}
int main(){
// io;
// int tt;cin>>tt;
// for(int _t = 1; _t <= tt; ++_t){
// printf("Case #%d: ", _t);
work();
// }
return 0;
}
9.Navigation Nightmare
题目描述：
有n个网格状的农田，每个农田之间有距离，会依次给出关系，在给出关系后询问两个农田之间的曼哈顿距离是多少？
若无法判断则输出-1。
思路：
离线边建图边查询
这里要维护曼哈顿距离，所以得用两个数组，一个表示x轴的距离，另一个表示y方向的距离
找爹和合并的过程就和之前的差不多
int fa[MAX]; int dix[MAX], diy[MAX]; int getfa(int x){ if(x != fa[x]){ int ff = fa[x]; fa[x] = getfa(fa[x]); dix[x] += dix[ff]; diy[x] += diy[ff]; } return fa[x]; } inline void emerge(int x, int y, int dx, int dy){ int xx = getfa(x); int yy = getfa(y); fa[xx] = yy; dix[xx] = dix[y] + dx - dix[x]; diy[xx] = diy[y] + dy - diy[x]; }离线边建图边查询，先建到该次查询的地方，再判断x和y在不在一个集合，不在就是-1，在的话就输出两个方向的差的绝对值的和就行
/*
Work by: Chelsea
Problem: 不知名屑题
Knowledge: 垃圾算法
Time: O(能过)
*/
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
//#include<unordered_map>
using namespace std;
//#pragma GCC optimize(2)
//#pragma GCC optimize(3)
//#pragma GCC optimize("inline")
//#pragma GCC optimize("-fgcse-lm")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
//#pragma GCC optimize("unroll-loops")
#define eps 1e-8
#define endl '\n'
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define NMAX 1000 + 50
#define ls p<<1
#define rs p<<1|1
//#define mod 1000000007
#define y1 y114514
#define lowbit(x) (x & (-x))
#define sz(s) (int)(s).size()
#define sd(n) scanf("%d",&n)
#define sl(n) scanf("%lld",&n)
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define sll(n,m) scanf("%lld %lld",&n,&m)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n",n, m)
#define sddd(n,m,z) scanf("%d %d %d",&n,&m,&z)
#define slll(n,m,z) scanf("%lld %lld %lld",&n,&m,&z)
#define io ios::sync_with_stdio(false);
#define mem(a,b) memset((a),(b),sizeof(a))
#define m_p(a,b) make_pair(a, b)
//#define int long long
typedef long long ll;
typedef pair <int,int> pii;
typedef unsigned long long ull;
//不开longlong见祖宗!
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}
//不改范围见祖宗!!!
#define MAX 300000 + 50
int n, m, k;
int x, y, z;
int a, b, c;
string s, t;
char op;
struct ran{
int x, y, z;
char op;
}tr[MAX];
int fa[MAX];
int dix[MAX], diy[MAX];
int getfa(int x){
if(x != fa[x]){
int ff = fa[x];
fa[x] = getfa(fa[x]);
dix[x] += dix[ff];
diy[x] += diy[ff];
}
return fa[x];
}
inline void emerge(int x, int y, int dx, int dy){
int xx = getfa(x);
int yy = getfa(y);
fa[xx] = yy;
dix[xx] = dix[y] + dx - dix[x];
diy[xx] = diy[y] + dy - diy[x];
}
void work(){
cin>>n>>m;
rep(i, 1, n)fa[i] = i;
rep(i, 1, m){
cin>>tr[i].x>>tr[i].y>>tr[i].z>>tr[i].op;
}
int pos = 1;
cin>>n;
rep(i, 1, n){
cin>>a>>b>>c;
rep(j, pos, c){
int dx = 0, dy = 0;
if(tr[j].op == 'E')dx = tr[j].z;
else if(tr[j].op == 'W')dx = -tr[j].z;
else if(tr[j].op == 'N')dy = tr[j].z;
else dy = -tr[j].z;
emerge(tr[j].x, tr[j].y, dx, dy);
}
pos = c + 1;
int xx = getfa(a);
int yy = getfa(b);
if(xx != yy)cout<<-1<<endl;
else cout<<abs(dix[a] - dix[b]) + abs(diy[a] - diy[b])<<endl;
}
}
int main(){
io
// int tt;cin>>tt;
// for(int _t = 1; _t <= tt; ++_t){
// printf("Case #%d: ", _t);
work();
// }
return 0;
}
10.A Bug's Life
题目描述：
n个昆虫，m个条件，每个昆虫只有两种性别，m个条件告诉的x和y是异性，问你这m个条件中会不会自相矛盾
思路：
和第八题的做法很像，可以说是一摸一样
同样可以用两种方法，一种是取模，另一种是多开一倍数组讨论
/*
Work by: Chelsea
Problem: 不知名屑题
Knowledge: 垃圾算法
Time: O(能过)
*/
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
//#include<unordered_map>
using namespace std;
//#pragma GCC optimize(2)
//#pragma GCC optimize(3)
//#pragma GCC optimize("inline")
//#pragma GCC optimize("-fgcse-lm")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
//#pragma GCC optimize("unroll-loops")
#define eps 1e-8
#define endl '\n'
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define NMAX 1000 + 50
#define ls p<<1
#define rs p<<1|1
//#define mod 1000000007
#define y1 y114514
#define lowbit(x) (x & (-x))
#define sz(s) (int)(s).size()
#define sd(n) scanf("%d",&n)
#define sl(n) scanf("%lld",&n)
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define sll(n,m) scanf("%lld %lld",&n,&m)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n",n, m)
#define sddd(n,m,z) scanf("%d %d %d",&n,&m,&z)
#define slll(n,m,z) scanf("%lld %lld %lld",&n,&m,&z)
#define io ios::sync_with_stdio(false);
#define mem(a,b) memset((a),(b),sizeof(a))
#define m_p(a,b) make_pair(a, b)
//#define int long long
typedef long long ll;
typedef pair <int,int> pii;
typedef unsigned long long ull;
//不开longlong见祖宗!
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}
//不改范围见祖宗!!!
#define MAX 300000 + 50
int n, m, k, op;
int x, y, z;
int a, b, c;
string s, t;
int fa[MAX];
int getfa(int x){
return x == fa[x] ? x : fa[x] = getfa(fa[x]);
}
inline void emerge(int x, int y){
fa[getfa(x)] = getfa(y);
}
void work(){
bool ans = 0;
sdd(n, m);
rep(i, 1, 2 * n)fa[i] = i;
rep(i, 1, m){
sdd(x, y);
if(ans)continue;
if(getfa(x) == getfa(y)){
ans = 1;
}
emerge(x, y + n);
emerge(x + n, y);
}
if(ans)cout<<"Suspicious bugs found!\n\n";
else cout<<"No suspicious bugs found!\n\n";
}
int main(){
// io
int tt;cin>>tt;
for(int _t = 1; _t <= tt; ++_t){
printf("Scenario #%d:\n", _t);
// printf("Case #%d: ", _t);
work();
}
return 0;
}
11.Rochambeau
题目描述：
n个人，m个已知条件，n个人中有一个法官，剩下n-1个人都是普通人，法官可以出任意的石头剪刀布，而剩下的人只能出一种且不可以变的手势
问谁是法官，且最小要多少个条件才能看出来是他法官
思路：
比较难的一个带权并查集
先枚举法官u，于u有关的关系就跳过，没关系的就合并判断，如果发现了矛盾的地方，就说明这个人不可能是法官
- 如果可能为裁判的孩子数量大于1，说明题目给出的信息是不可能出现的结果
- 如果没有找到可能为裁判的孩子，说明无法判断
- 如果可能为裁判的孩子数量为1，则该孩子是裁判，还需要判断是在第几句话之后发现该孩子是裁判的
- 在枚举的过程中，如果发现了矛盾会直接break（说明该孩子不可能是裁判），用pos变量记录当前是第几句话。而找到裁判需要排除其它所有的孩子，所以是pos的最大值。我们对其进行维护即可
/*
Work by: Chelsea
Problem: 不知名屑题
Knowledge: 垃圾算法
Time: O(能过)
*/
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
//#include<unordered_map>
using namespace std;
//#pragma GCC optimize(2)
//#pragma GCC optimize(3)
//#pragma GCC optimize("inline")
//#pragma GCC optimize("-fgcse-lm")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
//#pragma GCC optimize("unroll-loops")
#define eps 1e-8
#define endl '\n'
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define NMAX 1000 + 50
#define ls p<<1
#define rs p<<1|1
//#define mod 1000000007
#define y1 y114514
#define lowbit(x) (x & (-x))
#define sz(s) (int)(s).size()
#define sd(n) scanf("%d",&n)
#define sl(n) scanf("%lld",&n)
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define sll(n,m) scanf("%lld %lld",&n,&m)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n",n, m)
#define sddd(n,m,z) scanf("%d %d %d",&n,&m,&z)
#define slll(n,m,z) scanf("%lld %lld %lld",&n,&m,&z)
#define io ios::sync_with_stdio(false);
#define mem(a,b) memset((a),(b),sizeof(a))
#define m_p(a,b) make_pair(a, b)
//#define int long long
typedef long long ll;
typedef pair <int,int> pii;
typedef unsigned long long ull;
//不开longlong见祖宗!
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}
//不改范围见祖宗!!!
#define MAX 300000 + 50
int n, m, k;
int x, y, z;
int a, b, c;
string s, t;
char op;
struct ran{
int x, y, z;
char op;
}tr[MAX];
int fa[5005];
int val[5005];
int getfa(int x){
if(x != fa[x]){
int ff = fa[x];
fa[x] = getfa(fa[x]);
val[x] = (val[x] + val[ff]) % 3;
}
return fa[x];
}
bool emerge(int x, int y, int z){
int xx = getfa(x);
int yy = getfa(y);
if(xx == yy){
if(val[x] != ((val[y] + z) % 3))return false;
}
else{
fa[xx] = yy;
val[xx] = (val[y] + z - val[x] + 3) % 3;
}
return true;
}
int cuowu[5005];
void init(){
rep(i, 0, 505){
fa[i] = i;
val[i] = 0;
}
}
void work(){
while (cin>>n>>m) {
rep(i, 1, m){
cin>>tr[i].x>>tr[i].op>>tr[i].y;
if(tr[i].op == '=')tr[i].z = 0;
else if(tr[i].op == '>')tr[i].z = 1;
else tr[i].z = 2;
}
int mx = 0, ans = 0, num = 0;
rep(u, 0, n - 1){
init();
bool p = 0;
rep(i, 1, m){
if(tr[i].x == u || tr[i].y == u)continue;
if(!emerge(tr[i].x, tr[i].y, tr[i].z)){
mx = max(mx, i);
p = 1;
break;
}
}
if(!p){
++num;
ans = u;
}
}
if(n == 1)mx = 0;
if(num == 0)cout<<"Impossible\n";
else if(num == 1){
printf("Player %d can be determined to be the judge after %d lines\n", ans, mx);
}
else cout<<"Can not determine\n";
}
}
int main(){
// io;
// int tt;cin>>tt;
// for(int _t = 1; _t <= tt; ++_t){
// printf("Case #%d: ", _t);
work();
// }
return 0;
}
12.Connections in Galaxy War
题目描述：
每个星球只能向其能联系到的星球中power最大（如果有多个就取序号最小的）且power比自己大的星球求助。
一开始给出M条信息，形如：a b；代表a、b星球间可以相互联系到
然后给出Q条指令，query指令代表询问星球x会向哪个星球求助（或者输出-1代表没有求援对象）；destroy指令代表破坏星球x和星球y之间的联系。
思路：
点带权并查集，每个点都有一个权值
用并查集来维护能互相联系到的点，并让并查集的根节点(集合代表）是这个集合中权值最大且序号最小的元素。如何实现？只要在合并集合函数中进行判断即可，让权值大的点成为根节点。
问题出在拆边（destroy）上，并查集并无法实现这个功能。但是有一个很巧妙的做法，先记录Q条指令，对于不会被destroy的边，直接连起来。然后倒着处理这Q条指令，遇到destroy后将这条边在加上即可。
有几个要注意的地方：
- 每个星球只能向比自己power大的星球，所以如果这个星球所在集合的代表和这个星球power一样大（只是序号更小所以成为了集合代表），那么这个星球也是没法求援的。
- 两组输出的数据间需要加一个空行，最后一组数据不需要输出空行
- 记得初始化
/*
Work by: Chelsea
Problem: 不知名屑题
Knowledge: 垃圾算法
Time: O(能过)
*/
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
#include<unordered_map>
using namespace std;
//#pragma GCC optimize("Ofast")
//#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
//#pragma GCC optimize("unroll-loops")
#define eps 1e-8
#define endl '\n'
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define NMAX 1000 + 50
#define ls p<<1
#define rs p<<1|1
#define mod 998244353
#define lowbit(x) (x & (-x))
#define sz(s) (int)(s).size()
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define sl(n) scanf("%lld",&n)
#define sll(n,m) scanf("%lld %lld",&n,&m)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n",n, m)
#define sddd(n,m,z) scanf("%d %d %d",&n,&m,&z)
#define slll(n,m,z) scanf("%lld %lld %lld",&n,&m,&z)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
#define m_p(a,b) make_pair(a, b)
typedef long long ll;
typedef pair <int,int> pii;
typedef unsigned long long ull;
//不开longlong见祖宗!
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}
//不改范围见祖宗!!!
#define MAX 300000 + 50
int n, m, k, op;
int x, y, z;
int l, r;
string s, t;
struct ran{
string op;
int x, y;
}tr[MAX];
int val[MAX];
int fa[MAX];
void init(){
for(int i = 0; i <= n; ++i)fa[i] = i;
}
int getfa(int x){
return x == fa[x] ? x : fa[x] = getfa(fa[x]);
}
inline void emerge(int x, int y){
int xx = getfa(x);
int yy = getfa(y);
// cout<<xx<<' '<<val[xx]<<' '<<yy<<' '<<val[yy]<<endl;
if(val[xx] > val[yy])fa[yy] = xx;
else if(val[xx] < val[yy])fa[xx] = yy;
else{
if(xx < yy)fa[yy] = xx;
else fa[xx] = yy;
}
}
void work(){
int qq = 0;
while (sd(n) != EOF) {
++qq;
if(qq != 1)cout<<endl;
init();
map<pair<int, int>, int>mp;
for(int i = 0; i < n; ++i){
sd(val[i]);
}
sd(k);
vector<pair<int, int> >v;
for(int i = 1; i <= k; ++i){
cin>>x>>y;
if(x > y)swap(x, y);
v.push_back(m_p(x, y));
}
sd(m);
for(int i = 1; i <= m; ++i){
cin>>tr[i].op;
if(tr[i].op[0] == 'q')sd(tr[i].x);
else {
sdd(tr[i].x, tr[i].y);
if(tr[i].x > tr[i].y)swap(tr[i].x, tr[i].y);
mp[m_p(tr[i].x, tr[i].y)] = 1;
}
}
for(int i = 0; i < k; ++i){
if(!mp.count(v[i])){
emerge(v[i].first, v[i].second);
// cout<<v[i].first<<' '<<v[i].second<<endl;
}
}
// cout<<getfa(0)<<' '<<getfa(1)<<' '<<getfa(2)<<endl;
vector<int>ans;
for(int i = m; i >= 1; --i){
// cout<<tr[i].op<<' '<<tr[i].x<<' '<<tr[i].y<<endl;
if(tr[i].op[0] == 'q'){
int p = getfa(tr[i].x);
// cout<<p<<endl;
if(p == tr[i].x){
ans.push_back(-1);
}
else {
if(val[p] == val[tr[i].x])ans.push_back(-1);
else ans.push_back(p);
}
}
else{
// cout<<tr[i].x<<' '<<tr[i].y<<endl;
emerge(tr[i].x, tr[i].y);
// cout<<getfa(tr[i].x)<<' '<<getfa(tr[i].y)<<endl;
}
}
for(int i = (int)ans.size() - 1; i >= 0; --i)cout<<ans[i]<<endl;
}
}
int main(){
// io;
// int tt;cin>>tt;
// for(int _t = 1; _t <= tt; ++_t){
// printf("Case #%d: ", _t);
work();
// }
return 0;
}
/*
3
20 20 20
3
1 2
0 1
0 2
4
query 1
query 2
destroy 1 2
query 2
-1
-1
-1
3
10 20 10
2
1 2
0 1
5
query 0
query 1
query 2
destroy 1 2
query 2
1
-1
1
-1
*/
13.小希的迷宫
题目描述：
给一堆无向边，问能不能组成一颗树
思路：
如果输入的过程中所有点在合并前都不联通，而且输入的边的数量等于点的数量-1，才是Yes，否则是No
/*
Work by: Chelsea
Problem: 不知名屑题
Knowledge: 垃圾算法
Time: O(能过)
*/
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
//#include<unordered_map>
using namespace std;
//#pragma GCC optimize("Ofast")
//#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
//#pragma GCC optimize("unroll-loops")
#define eps 1e-8
#define endl '\n'
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define NMAX 1000 + 50
#define ls p<<1
#define rs p<<1|1
#define mod 998244353
#define lowbit(x) (x & (-x))
#define sz(s) (int)(s).size()
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define sl(n) scanf("%lld",&n)
#define sll(n,m) scanf("%lld %lld",&n,&m)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n",n, m)
#define sddd(n,m,z) scanf("%d %d %d",&n,&m,&z)
#define slll(n,m,z) scanf("%lld %lld %lld",&n,&m,&z)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
#define m_p(a,b) make_pair(a, b)
//#define int long long
typedef long long ll;
typedef pair <int,int> pii;
typedef unsigned long long ull;
//不开longlong见祖宗!
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}
//不改范围见祖宗!!!
#define MAX 300000 + 50
int n, m, k, op;
int x, y, z;
ll a, b, c;
string s, t;
int fa[MAX];
int getfa(int x){
return x == fa[x] ? x : fa[x] = getfa(fa[x]);
}
inline void emerge(int x, int y){
fa[getfa(x)] = getfa(y);
}
bool cal(){
int bian = 1;
set<int>dian;
bool p = 1;
dian.insert(x);dian.insert(y);
while (cin>> x >> y) {
if(x == 0 && y == 0){
break;
}
++bian;
dian.insert(x);
dian.insert(y);
int xx = getfa(x);
int yy = getfa(y);
if(xx == yy){
p = 0;
}
emerge(x, y);
}
if(bian != dian.size() - 1)p = 0;
return p;
}
void work(){
while (cin>>x>>y) {
if(x == 0 && y == 0){
printf("Yes\n");
}
else{
if(x == -1 && y == -1)break;
for(int i = 0; i <= 100000; ++i)fa[i] = i;
emerge(x, y);
if(cal())printf("Yes\n");
else printf("No\n");
}
}
}
int main(){
io;
// int tt;cin>>tt;
// for(int _t = 1; _t <= tt; ++_t){
// printf("Case #%d: ", _t);
work();
// }
return 0;
}
14.Is It A Tree?
同13
