NC20566（[SCOI2010]游戏）

感受



思路

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int maxn = 10000 + 10;
int m;
int fa[maxn];
int num[maxn];
bool vis[maxn];
void init(){
    int ma = maxn - 5;
    for(int i = 1; i <= ma; i++){
        fa[i] = i; num[i] = 1;
    }
}
int find_fa(int x){
    return x == fa[x] ? x : fa[x] = find_fa(fa[x]);
}
bool flag[maxn];
int main(){
    scanf("%d", &m);
    init();
    int u, v;
    for(int i = 1; i <= m; i++){
        scanf("%d%d", &u, &v);
        u = find_fa(u); v = find_fa(v);
        if(u == v) vis[u] = true;
        else{
            fa[u] = v;
            if(vis[u]) vis[v] = true;
            num[v] += num[u];
        }
    }
    for(int i = 1, rt; i <= 10000; i++){
        rt = find_fa(i);
        if(!vis[rt]){
            if(num[rt] > 1){
                flag[i] = true; num[rt]--;
            }
        }///连通块中无环
        else{
            flag[i] = true;
        }///有环
    }
    for(int i = 1; i <= 10001; i++){
        if(!flag[i]){
            printf("%d\n", i - 1); break;
        }
    }
    return 0;
}