【数据范围】
对于30%的数据，保证N < =1000
对于100%的数据，保证N < =1000000
题解
一个武器可以看成连接对应两个属性值的一条边
可以证明如果一个联通块中出现一个环
则整个联通块都可以取
否则会有一个点不能取
显然这个不取的点是最大的那个点= =
然后扫一遍看能取到哪就行了
找环和维护最大可以用并查集做
//转载的，太神啦！！！！
#include <cstdio> #include <iostream> #include <cstring> #include <algorithm> #include <string> #include <queue> #include <stack> #include <cmath> #include <map> #include <vector> #include <functional> #include <ctime> #include <cstdlib> #include <sstream> #include <set> #include <deque> using namespace std; typedef long long ll; typedef long double ld; const int maxn = 1000005; int n, fa[maxn], is[maxn]; int getfa(int now) { return (!fa[now]) ? now : fa[now] = getfa(fa[now]); } int main() { scanf("%d", &n); for (int i = 0; i < n; ++i) { int u, v; scanf("%d%d", &u, &v); u = getfa(u), v = getfa(v); if (u == v) is[u] = is[v] = 1; else { if (u < v)swap(u, v); if (is[u] || is[v]) is[u] = is[v] = 1; fa[v] = u; is[v] = 1; } } for (int i = 1; i < maxn; ++i) if (!is[i]) { cout << i - 1; break; } }
原文：http://www.cnblogs.com/qscqesze/p/4348774.html