开发者社区云计算文章正文

uva 1160 X-Plosives

2013-07-26 749

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 点击打开链接uva 1160 思路: 并查集分析: 1 看懂题目之和就是切菜了代码: #include#include#include#includeusing namespace std;const int MAXN...

点击打开链接uva 1160

思路: 并查集
分析:
1 看懂题目之和就是切菜了

代码:

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int MAXN = 100010;

int father[MAXN];

int find(int x){
    if(father[x] != x)
        father[x] = find(father[x]);
    return father[x];
}

int main(){
    int x , y , ans;
    while(scanf("%d" , &x) != EOF){ 
        scanf("%d" , &y);
        for(int i = 0 ; i < MAXN ; i++)
            father[i] = i;
        father[x] = y;
        ans = 0;
        while(scanf("%d" , &x) && x != -1){
            scanf("%d" , &y); 
            int fx = find(x); 
            int fy = find(y);
            if(fx == fy)
                ans++;
            else
                father[fx] = fy;
        }
        printf("%d\n" , ans);            
    }
    return 0;
}