L - 小希的迷宫——并查集_环

曾经终败给现在 2022-06-12 11:57 154阅读 0赞

Think:  
1知识点：并查集集合内判断环的存在+并查集判断集合数目  
2反思：  
1>题目分析基本完备再代码实现，不要急于求成  
2>初始思路错误采取新思路应考虑之前思路可以判断的情况当前思路是否可以判断

[vjudge题目链接][vjudge]

[参考代码1——并查集集合内判断环的存在][1]  
[参考代码2——题意条件分析][2]

以下为Wrong Answer代码——判断条件不全面

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    const int N = 1e5 + 4;
    
    int ans, f[N], vis[N];
    
    void Init();
    int get_f(int x);
    void Merge(int u, int v);
    
    int main(){
        int u, v, mav;
        while(scanf("%d %d", &u, &v) && (u != -1 && v != -1)){
            ans = 0;
            memset(vis, 0, sizeof(vis));
            vis[u] = 1, vis[v] = 1;
            mav = max(u, v);
    
            Init();
    
            Merge(u, v);
            while(scanf("%d %d", &u, &v) && (u != 0 || v != 0)){
                Merge(u, v);
                vis[u] = 1, vis[v] = 1;
                mav = max(mav, u);
                mav = max(mav, v);
            }
    
            if(!ans)
                printf("Yes\n");
            else
                printf("No\n");
        }
        return 0;
    }
    void Init(){
        for(int i = 1; i <= N; i++)
            f[i] = i;
    }
    void Merge(int u, int v){
        int t1 = get_f(u);
        int t2 = get_f(v);
        if(t1 == t2)
            ans++;
        else {
            f[t2] = t1;
        }
    }
    int get_f(int x){
        if(f[x] == x)
            return f[x];
        else {
            f[x] = get_f(f[x]);
            return f[x];
        }
    }

以下为Accepted代码

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    const int N = 1e5 + 4;
    
    int ans, f[N], vis[N];
    
    void Init();
    int get_f(int x);
    void Merge(int u, int v);
    
    int main(){
        int u, v, mav, miv, i, cnt;
        while(scanf("%d %d", &u, &v) && (u != -1 && v != -1)){
            if(u == 0 && v == 0){
                printf("Yes\n");
                continue;
            }
    
            ans = 0, cnt = 0;
            memset(vis, 0, sizeof(vis));
            vis[u] = 1, vis[v] = 1;
            mav = max(u, v);
            miv = min(u, v);
    
            Init();
            Merge(u, v);
    
            while(scanf("%d %d", &u, &v) && (u || v)){
                Merge(u, v);
                vis[u] = 1, vis[v] = 1;
    
                mav = max(mav, u);
                mav = max(mav, v);
    
                miv = min(miv, u);
                miv = min(miv, v);
            }
    
            for(i = miv; i <= mav; i++){
                if(vis[i] && f[i] == i)
                    cnt++;
            }
    
    
            if((!ans) && cnt == 1)
                printf("Yes\n");
            else
                printf("No\n");
        }
        return 0;
    }
    void Init(){
        for(int i = 1; i <= N; i++)
            f[i] = i;
    }
    void Merge(int u, int v){
        int t1 = get_f(u);
        int t2 = get_f(v);
        if(t1 == t2)
            ans++;
        else {
            f[t2] = t1;
        }
    }
    int get_f(int x){
        if(f[x] == x)
            return f[x];
        else {
            f[x] = get_f(f[x]);
            return f[x];
        }
    }

[vjudge]: https://vjudge.net/contest/163007#problem/L
[1]: http://blog.csdn.net/qq415200973/article/details/10299823
[2]: http://blog.csdn.net/l55iuming/article/details/46402691