美文网首页
LA 3644(并查集)

LA 3644(并查集)

作者: laochonger | 来源:发表于2018-05-05 14:35 被阅读0次

题意:判断是否成环,成环则error++
使用并查集进行判断即可,另外,题目要求的输入判断也是一个注意点

#include<iostream>
using namespace std;

const int maxn = 100005;
int pre[maxn];

int find(int x){
    return pre[x] == x?x:pre[x] = find(pre[x]); 
}

int main(){
    int a,b;
    while(scanf("%d", &a) == 1){
        for(int i = 0; i <= maxn; i++) pre[i] = i;
        int error = 0;
        while(a!=-1){
            scanf("%d", &b);
            a = find(a);
            b = find(b);
            if(a==b){
                error++;
            }else{
                pre[a] = b;
            }
            scanf("%d", &a);
        }
        printf("%d\n", error);
    }
    return 0;
}

相关文章

  • LA 3644(并查集)

    题意:判断是否成环,成环则error++使用并查集进行判断即可,另外,题目要求的输入判断也是一个注意点

  • LA 3027(并查集)

    wa了一次,忘记初始化d[i];对于单个字符的输入,可以使用一整个字符串输入,避免出现读取空格的错误并查集并不一定...

  • markdown学习

    #并查集 ##并查集的定义 ##并查集的操作

  • 算法模板(四)并查集

    并查集 路径压缩并查集

  • 并查集入门使用

    本文参考自《算法笔记》并查集篇 并查集的定义 什么是并查集?并查集可以理解为是一种维护数据集合的结构。名字中并查集...

  • 并查集练习

    并查集 参考《算法笔记》 三要素:并,查,集。 并差集与一个算法有关,kruskal算法,就可通过并查集实现。 1...

  • 并查集

    并查集 并查集是什么 并查集是一种用来管理元素分组情况的数据结构,并查集可以高效地进行如下操作: 查询元素a和元素...

  • 数据结构与算法(十二)并查集(Union Find)

    本文主要包括以下内容: 并查集的概念 并查集的操作 并查集的实现和优化Quick FindQuick Union基...

  • 并查集

    并查集是什么 并查集是一种用来管理元素分组情况的数据结构。并查集可以高效地进行如下操作。不过需要注意并查集虽然可以...

  • 并查集

    开始时让每个元素构成一个个单元素集合(注意初始化时应使每个元素各成一组)按照一定顺序将属于同一组元素所在的集合合并...

网友评论

      本文标题:LA 3644(并查集)

      本文链接:https://www.haomeiwen.com/subject/blzsrftx.html