2020-5-20-POJ 1182-关系型并查集

短命女 2023-01-23 01:57 6阅读 0赞

# 并查集： #

[POJ 1182][]

#include<bits/stdc++.h>
    #define rep(i,a,b) for(int i=a;i<=b;++i)
    const int N = 5e4;
    using namespace std;
    
    int n;
    int pre[N+10], rela[N+10];
    
    int find(int x)
    { 
    	int y=x,cnt=0;
    	while(y!=pre[y]){ 
    	 // 加上逻辑距离
    		cnt+=rela[y];
    		
    		y=pre[y];
    	}
    	while(x!=pre[x]){ 
    		int px = pre[x];
            
    		int tmp = rela[x];
    		rela[x] = cnt;
    		cnt -= tmp;
    		
    		pre[x] = y;
    		x = px;
    	}
    	return y;
    }
    
    void Union(int op, int x, int y)
    { 	
    	int rx = find(x);
    	int ry = find(y);
    	pre[rx] = ry;
    	rela[rx] = op + rela[y] - rela[x]; // 将距离进行向量加减
    }
    
    int main()
    { 
        int k, sum = 0; scanf("%d %d", &n, &k);
        rep(i,1,n) pre[i] = i, rela[i] = 0; // 记录关系的数组
        while(k--)
        { 
            int op, x, y;
        	scanf("%d %d %d", &op, &x, &y);
        	if (x>n || y>n || (x==y && op==2)) { sum++;continue;} // 第二个和第三个条件
        	op--; // 
        	int xx = find(x);
        	int yy = find(y);
        	if (xx != yy) Union(op, x, y);
        	else // 判断第一个条件
        	{ 
        		if(((rela[x]-rela[y])%3+3)%3==op) continue;
        		else sum++;
        	}
        }
        printf("%d\n",sum);
        return 0;
    }

还是比较菜，这一题研究很久

这一题也是很简单,思路就不说了

[http://acm.hdu.edu.cn/showproblem.php?pid=1213][http_acm.hdu.edu.cn_showproblem.php_pid_1213]

#include<bits/stdc++.h>
    #define rep(i,a,b) for(int i=a;i<=b;++i)
    const int N = 5e4;
    using namespace std;
    
    int pre[N+10];
    
    int finds(int x)
    { 
    	int y = x;
    	while(y!=pre[y])
    	{ 
    		y = pre[y];
    	}
    	while(x!=pre[x])
    	{ 
    		int px = pre[x];
    		pre[x] = y;
    		x = px;
    	}
    	return y;
    }
    
    void Union(int a, int b)
    { 
    	pre[a] = b;
    }
    int main()
    { 
    	int t;
    	scanf("%d",&t);
    	while(t--)
    	{ 
    		int n, m, ans=0;
    		scanf("%d %d",&n, &m);
    		rep(i,1,n) pre[i] = i;
    		while(m--)
    		{ 
    			int a, b;
    			scanf("%d %d",&a, &b);
    			int xx = finds(a);
    			int yy = finds(b);
    			if(yy!=xx){ 
    				Union(xx, yy);
    			}
    		}
    		rep(i,1,n) if(pre[i]==i) ans++;
    		printf("%d\n", ans);
    
    	}
    }

如果数据比较小的话，查找的操作的可简便一点  
也为了再练一遍手速

#include<bits/stdc++.h>
    using namespace std;
    
    int pre[10010];
    
    int finds(int x)
    { 
    	while(x!=pre[x])
    	     x = pre[x];
    	return x;
    }
    
    void Union(int a, int b)
    { 
    	pre[a] = b;
    }
    
    int main()
    { 
    	int t; scanf("%d", &t);
    	while(t--){ 
    		int n, m, ans = 0;
    		scanf("%d %d", &n, &m);
    		for (int i = 1; i <= n; i++) pre[i] = i;
    		while(m--)
    		{ 
    			int a, b; scanf("%d %d", &a, &b);
    			int xx = finds(a);
    			int yy = finds(b);
    			if(xx!=yy) Union(xx, yy);
    		}
    		for (int i = 1; i <= n; i++) if (pre[i]==i) ans++;
    			printf("%d\n", ans);
    	}
    	return 0;
    }

[POJ 1182]: http://poj.org/problem?id=1182
[http_acm.hdu.edu.cn_showproblem.php_pid_1213]: http://acm.hdu.edu.cn/showproblem.php?pid=1213