Description
lxhgww最近迷上了一款游戏，在游戏里，他拥有很多的装备，每种装备都有2个属性，这些属性的值用[1,10000]之间的数表示。当他使用某种装备时，他只能使用该装备的某一个属性。并且每种装备最多只能使用一次。 游戏进行到最后，lxhgww遇到了终极boss，这个终极boss很奇怪，攻击他的装备所使用的属性值必须从1开始连续递增地攻击，才能对boss产生伤害。也就是说一开始的时候，lxhgww只能使用某个属性值为1的装备攻击boss，然后只能使用某个属性值为2的装备攻击boss，然后只能使用某个属性值为3的装备攻击boss……以此类推。 现在lxhgww想知道他最多能连续攻击boss多少次？
Input
输入的第一行是一个整数N，表示lxhgww拥有N种装备 接下来N行，是对这N种装备的描述，每行2个数字，表示第i种装备的2个属性值
Output
输出一行，包括1个数字，表示lxhgww最多能连续攻击的次数。
Sample Input
3
1 2
3 2
4 5
Sample Output
2
HINT
【数据范围】
对于30%的数据，保证N < =1000
对于100%的数据，保证N < =1000000
Source
Day1
思路：
又想了一想，贪心不就行了？？感觉和并查集是等价的啊
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;const int maxn = 1e6 + 7;
const int mod = 998244353;
typedef long long ll;int dp[maxn];int main() {int n;scanf("%d",&n);for(int i = 1;i <= n;i++) {int x,y;scanf("%d%d",&x,&y);if(x > y)swap(x,y);if(dp[x]) {dp[y] = 1;} else {dp[x] = 1;}}for(int i = 1;i < maxn;i++) {if(!dp[i]) {printf("%d\n",i - 1);return 0;}}return 0;
}玄妙无比的一道题。和匹配很像，但正解是建图并查集。
将lxhgww的两个属性所属连通分量根节点中小的值连接在大的值上面，最后构成一个森林。这个森林的意义是：每一棵树的根节点大于子节点，且根节点不一定能取，子节点一定能取。
那么两个点对应的根节点相同的时候，此时x到rx存在一条路径，假设为x->x1->x2->rx，则一定有一个装备属性为(x,x1)，一个装备属性为(x1,x2)，一个装备属性为(x2,rx)，此时多了一个x，替换掉原来的x，则多了一个x1。替换掉原来的x1，则多了一个x2，最后就能得到rx，所以此时保证rx一定能取。
如果两个点对应的根节点不同，如果其中一个根节点能取，那么两个点对应的根节点都能取到。否则只能取较小的那个点。
#include <cstdio>
#include <algorithm>
using namespace std;const int maxn = 1000000 + 7;
int fa[maxn],vis[maxn];int findset(int x)
{return fa[x] == 0 ? x : fa[x] = findset(fa[x]);
}
int main()
{int n;scanf("%d",&n);for(int i = 1 ;i <= n;i++){int x,y;scanf("%d%d",&x,&y);int rx = findset(x),ry = findset(y);if(rx == ry){vis[rx] = vis[ry] = 1;}else{if(rx < ry)swap(rx,ry);if(vis[rx] || vis[ry])vis[rx] = vis[ry] = 1;fa[ry] = rx;vis[ry] = 1;}}for(int i = 1;i <= maxn;i++){if(!vis[i]){printf("%d\n",i - 1);return 0;}}
}