codeforces 691D Swaps in Permutation（并查集）-白红宇

codeforces 691D Swaps in Permutation（并查集）

阅读量：6370 次

发布时间：2019-06-23

本文共 990 字，大约阅读时间需要 3 分钟。

题意：

给你一个长度为n的数列，然后给你m组数，

表示这两个数可以交换

然后让你给出字典序最大的数列

思路：

用并查集，可交换的数都是成组的，把同一并查集中的数加在根节点的vector后，

在一个并查集中的数，从大到输出就好了

/* ***********************************************Author        :devil************************************************ */#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            #include 
             
              #include 
              
               #include 
               
                using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=1e6+10;int a[N],pre[N],cnt[N];vector
                
                 eg[N];int find(int x)//查找根节点{ int r=x; while(pre[r]!=r)//返回根节点r r=pre[r]; int i=x,j; while(i!=r)//路径压缩 { j=pre[i];//在改变上级之前用临时变量j记录下他的值 pre[i]=r;//把上级改为根节点 i=j; } return r;}void join(int x,int y)//判断x,y是否连通.如果已经连通,就不用管了;如果不连通,就把它们所在的连通分支合并起{ int fx=find(x),fy=find(y); if(fx!=fy) pre[fx]=fy;}int main(){ //freopen("in.txt","r",stdin); int n,m,x,y; scanf("%d%d",&n,&m); for(int i=0;i