Artwork Gym - 101550A(并查集)

港控/mmm° 2024-04-18 10:53 85阅读 0赞

[题目连接——][Link 1]

###### 起初： ######

这个题是关于图的**连通分量**的。  
对于连通分量，**bfs和dfs染色**的方式进行，判断连通分量的个数。  
也可以通过**并查集**，判断连通分量的个数。

如果每次 数组标记+通过bfs和dfs的方式来统计连通分量的个数，肯定会超时。

###### 补题: ######

听了其他人的讲解， 从**最后一个状态到第一个状态**， 这样**逆序**来求答案。  
①即先将图涂成最后一个状态，通过并查集判断最后一个状态的连通分量个数。

②存下当前状态的答案， 然后去掉这一次询问颜色，通过并查集和一些小处理  
判断图的连通分量，求出下一个状态的连通分量个数。

③重复第二次操作。

###### 注意： ######

个人感觉该题 图文有点问题，与我们敲acm的思维不太一样  
该题需要将二维转化为一维， 然后利用并查集

##### 代码有点乱 #####

/****** 注：该题图与数配对与我个人思维 有差异， 所以 我将看成了 n行 m列的图， 如果根据样例我将他看成 6行4列的图， x表示行 y表示列 所以我将 x行y列的 即[x][y] 转换成了 x*m+y *****************/
    #include<bits/stdc++.h>
    
    using namespace std;
    
    const long maxn = 1e4+5;
    
    struct modify// 
    { 
        long x,  y;// 涂色的坐标
        long num;// 最早在那一次被涂色
    };
    
    priority_queue<modify>que;
    
    bool operator < (modify a, modify b)
    { 
        return a.num < b.num;
    }
    
    long par[1010005];//并查集
    long G[1010005];// 图
    long ans[maxn];// 答案
    
    void init(long m, long n)
    { 
        for(long i = 1; i <= n; i++)
        { 
            for(long j = 1; j <= m; j++)
            { 
                par[i*m+j] = i*m+j;
            }
        }
    }
    long found(long x)
    { 
        if(par[x] == x)
        { 
            return par[x];
        }
        else
        { 
            par[x] = found(par[x]);
            return par[x];
        }
    
    }
    bool unite(long x, long y)
    { 
        long rootx = found(x);
        long rooty = found(y);
        if(rootx == rooty)return false;
        else
        { 
            par[rootx] = rooty;
            return true;
        }
    }
    long cnt = 0;
    void process(long n, long m)
    { 
        /**通过并查集， 进行连通过程*/
        for(long i = 1; i <= n; i++)
        { 
            
            for(long j = 1; j <= m; j++)
            { 
                if(!G[i*m+j])// 如果没被染色
                { 
                    int o = (i-1)*m+j;
                    int oo = i*m+j;
                    if((i-1)>=1&&!G[o])//上
                    { 
                        unite(oo, o);
                    }
                    o = (i+1)*m+j;
                    if((i+1)<=n&&!G[o])//下
                    { 
                        unite(oo, o);
                    }
                    o = i*m+j-1;
                    if((j-1)>=1&&!G[o])// 左
                    { 
                        unite(oo, o);
                    }
                    o = i*m+j+1;
                    if((j+1)<= m&&!G[o])// 右
                    { 
                        unite(oo, o);
                    }
                }
    
            }
    
        }
        
        //统计连通分量， 并将染色块相关信息压入优先队列 过程 
        for(long i = 1; i <= n; i++) 
        { 
            for(long j = 1; j <= m; j++)
            { 
                modify tmp;
                tmp.num = G[i*m+j];
                tmp.x = i;
                tmp.y = j;
                if(!G[i*m+j]&&par[i*m+j] == i*m+j)cnt++;
                else que.push(tmp);//
            }
        }
    }
    long q;
    void input(long n, long m)
    { 
        long x1, x2, y1, y2;
         for(long i = 1; i <= q; i++)
        { 
            cin>>x1>>y1>>x2>>y2;
            for(long x = x1; x <= x2; x++)
            { 
                for(long y = y1; y <= y2; y++)
                { 
                    if(!G[y*m+x])G[y*m+x] = i; // 用图标记他最早是在哪一次被染色
    
                }
            }
        }
    }
    int main()
    { 
        memset(G, 0, sizeof(G));// 初始化图 为0 表示没被染过色
    
        ios_base::sync_with_stdio(false);
        long n, m;// n是行 m是列
    
        cin>>m>>n>>q;// 注意我的输入顺序
        init(m, n);// 初始化并查集
        input(n, m);
    
        process(n, m);
    
    
    
    
        for(long k = q; k >=1; k--)
        { 
            ans[k] = cnt;// 先存当前的答案
    
            while(!que.empty()&&que.top().num == k)// 把最早在该次颜色的块去掉， 让他进入上一个状态
            { 
                modify tmp = que.top();
                long i = tmp.x;
                long j = tmp.y;
                G[i*m+j] = 0;
                que.pop();
                int oo = i*m+j;
                int o = (i-1)*m+j;
                int f = 0;
    
                if((i-1)>=1&&!G[o])//上
                { 
    
                    if(unite(oo, o))
                    { 
    
                        f++;
                    }
                }
                o = (i+1)*m+j;
                if((i+1)<=n&&!G[o])//下
                { 
    
                    if(unite(oo, o))
                    { 
    
                        f++;
                    }
                }
                o = i*m+j-1;
                if(j-1>= 1&&!G[o])// 左
                { 
                    if(unite(oo, o) )
                    { 
    
                        f++;
                    }
                }
                o = i*m+j+1;
                if(j+1<= m&&!G[o])// 右
                { 
                    if(unite(oo, o))
                    { 
                        f++;
                    }
                }
                
                if(!f)cnt++; // 如果 没有与当前块相连的 连通分量就加一
                else cnt-=(f-1);// 如果有 f分量个一该块 相连的， 连通分连就减少 f-1
            }
        }
        
        for(long i = 1; i <= q; i++)// 输出答案
        { 
            cout<<ans[i]<<endl;
        }
    
    
        return 0;
    }

[Link 1]: https://vjudge.net/problem/Gym-101550A