题解 | #Jump#

对前辈代码的小小见解

#include <iostream>

using namespace std;
const int N = 1e4+10;
int f[N];
bool visit[N];

int find(int x){    //寻找祖节点
    if(f[x] != x) f[x]=find(f[x]);
    return f[x];
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    for(int i=1;i<=10000;i++){
        f[i] = i;
    }
    int n;
    cin>>n;
    while(n--){  //每个集合中只有祖节点没有被确认!!!
  				 //每次循环只确定一个值
        int x,y;
        cin>>x>>y;
        int fx = find(x),fy = find(y);
        
        if(fx>fy) swap(fx,fy);
        if(fx==fy) visit[fx] = 1; 
        else{
            f[fx] = fy; 					//将两个集合合并，x所在集合变为fy的分支
            if(!visit[fx]) visit[fx] = 1; //此时只有祖节点fx和fy没被确定，如果fx没被定,
            else visit[fy] = 1; 			//则优先确定较小值fx,否则 确定唯一没被确定的祖节点fy
        }
    }
    
    int cnt = 0;
    for(int i=1;i<=10000;i++){ //循环遍历所有值，如果出现中断则终止
        if(visit[i]) cnt++;
        else break;
    }
    cout<<cnt;
    return 0;
}