题解 | #[SCOI2010]游戏#

[SCOI2010]游戏

https://ac.nowcoder.com/acm/problem/20566

本题将每件装备的两个点连成线，变成图。如果某个区域里面的图是一个树的话证明有一个是取不到的数，这时候必然将最大的去掉才为最好啊。

如果不是一个数，也就是有一个或多个回路的话证明每个数都可以取到。那么最后取组成为数里面的最大数，取最大数里面的最小的那个数就是最早阶段的地方，这个地方就是答案。

可以使用DFS搜索，如果搜索过程中碰到了之后搜索过的而且不是父亲的点，证明出现了回路。如果没有这样的情况那么就需要去最大的数了。

#include <bits/stdc++.h>
 
 
using namespace std;
const int maxn = 1000000+10;
vector<int> edge[maxn];
bool vis[maxn];
int max_val;
int N;
 
int dfs(int x, int fa) {
    bool flag = 0;
    max_val = max(max_val, x);
    for (int i=0;i<edge[x].size();i++) {
        if (edge[x][i]==fa) continue;
        if (vis[edge[x][i]]) {flag = 1; continue;}
        vis[edge[x][i]] = true;
        if (dfs(edge[x][i], x)) 
            flag = 1;
    }
    return flag;
}
 
int main() {
    int x, y;
    int ans = INT_MAX;
    cin>>N;
    for (int i=0;i<N;i++) {
        cin>>x>>y;
        edge[x].push_back(y);
        edge[y].push_back(x);
    }
    ans = N+1;
    for (int i=1;i<=N+1;i++) {
        max_val = 0;
        if (vis[i]) continue;
        if (!dfs(i, 0)) {
            ans = min(ans, max_val);
        }
    }
    cout<<ans-1;
    return 0;
}

采用并查集的做法：使用并查集的时候如果合并的两个的根相同的话证明发生了回路的情况，那么就将根部的状态变成1证明有回路。如果不同的话就变成两个根状态的或值，因为如果有回路的话合并后同样受感染有了回路。之后再根的地方记录其最大值即可。

#include <bits/stdc++.h>


using namespace std;
const int maxn = 10000+10;
int a[maxn], b[maxn], max_val[maxn];
int N;

int find(int x) {
    return a[x]==x? x:a[x] = find(a[x]);
}
int main() {
    int x, y;
    cin>>N;
    for (int i=1;i<=maxn-1;i++) {
        a[i] = i; max_val[i] = i;
        b[i] = 0;
    }
    for (int i=1;i<=N;i++) {
        cin>>x>>y;
        int rootx = find(x);
        int rooty = find(y);
        if (rootx != rooty) {
            a[rootx] = rooty;
            max_val[rooty] = max(max_val[rooty], max_val[rootx]);
            b[rooty] =(b[rooty] || b[rootx]);
        } else {
            b[rooty] = 1;
        }
    }
    int ans = 10001;
    //找最小截断
    for (int i=1;i<=maxn-1;i++) {
        if (a[i]==i && b[i]==0) {
            ans = min(ans, max_val[i]);
        }
    }
    cout<<ans-1;
    return 0;
}