首页 > 其他分享 >A. Learning Languages

A. Learning Languages

时间:2024-03-07 21:11:17浏览次数:22  
标签:pre return int dsu Languages fa findSet Learning

https://codeforces.com/problemset/problem/277/A

It presents a problem that we need to make all element connected, it can be solved by using dsu.
I didn't use my dsu model and write a simple version of Dsu.

class DSU{
public:
    DSU(int m): size_(m){
        fa_.resize(m);
        std::iota(fa_.begin(), fa_.end(), 0);
    }

    int findSet(int x){
        return fa_[x] == x ? x : fa_[x] = findSet(fa_[x]);
    }

    bool isSameSet(int x, int y){
        return findSet(x) == findSet(y);

    }

    bool unionSet(int u, int v){
        u = findSet(u);
        v = findSet(v);
        if (u == v){
            return false;
        }
        return fa_[u] = v, true;
    }

private:
    vector<int> fa_;
    int size_;
};

void solve(){
    int n, m;
    cin >> n >> m;

    DSU dsu(m + 1);
    vector<int> vis(m + 1);
    int ans = 0;
    for (int i = 0; i < n; ++i){
        int k;
        cin >> k;
        if (!k){
            ans ++;
        }
        int pre = -1;
        while (k --){
            int t;
            cin >> t;
            if (pre != -1){
                dsu.unionSet(pre, t);
            }
            pre = t;
            vis[t] = true;
        }
    }

    for (int i = 1; i <= m; ++i){
        for (int j = i + 1; j <= m; ++j){
            if (vis[i] && vis[j] && dsu.isSameSet(i, j) == false){
                dsu.unionSet(i, j);
                ans ++;
            }
        }
    }

    cout << ans << '\n';
}

标签:pre,return,int,dsu,Languages,fa,findSet,Learning
From: https://www.cnblogs.com/yxcblogs/p/18059768

相关文章

  • Contrastive Learning 对比学习 | 何恺明大神的 SimSiam
    论文题目:ExploringSimpleSiameseRepresentationLearning,CVPR2021。pdf:https://arxiv.org/abs/2011.10566相关博客:知乎|无门槛级讲解对比学习中的自监督模型Simsiam(通俗易懂)知乎|对比学习(ContrastiveLearning):研究进展精要(解释了为什么Simsiam会演变成这样)知......
  • Distance Learning Courses in MAC
    这道题目其实我们如果位运算的题目有取值范围的话(这道题目的\([x,y]\)),我们可以统计公共前缀首先对于一个数对\((x_i,y_i)\)(假设\(x_i≠y_i\)),我们先统计他们的最长公共前缀比如\(000110101\)和\(000111000\),他们的最长公共前缀就是\(000110000\)(位数都是\(32\)位,这里省略了,公共前......
  • CF1935E Distance Learning Courses in MAC
    CF1935EDistanceLearningCoursesinMAC题目大意给定\(n\)个变量\(z_i\in[x_i,y_i]\),你可以在范围内任意指定\(z_i\)的值。\(q\)次查询,每次查询给定区间\([l_i,r_i]\),求用这些变量得到的二进制或最大值。思路选择\(z\in[x,y]\),贡献分为两部分(1)\([x,y]\)的......
  • Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Probl
    发表时间:2020文章要点:这篇文章主要介绍当前offlineRL的研究进展,可能的问题以及一些解决方法。作者先介绍了强化学习的准备知识,比如policygradients,Approximatedynamicprogramming,Actor-criticalgorithms,Model-basedreinforcementlearning,这里不具体说了。接着开始说offl......
  • 《A Hierarchical Framework for Relation Extraction with Reinforcement Learning》
    代码原文地址摘要现有的大多数方法在确定关系类型之前,需要先识别出所有的实体,这样就忽略了实体提及和关系类型之间的交互。本文提出了一种新颖的联合抽取范式,把相关实体看作是关系的参数(首先检测一个关系,然后提取相应的实体作为关系的参数)。本文在这个范式下采用了一个分层......
  • Graph Contrastive Learning with Adaptive Augmentation 论文阅读笔记
    Abstract​ 尽管图CL方法得到了繁荣的发展,但图增强方案的设计——CL中的一个关键组成部分——仍然很少被探索。我们认为,数据增强方案应该保留图的内在结构和属性,这将迫使模型学习对不重要的节点和边缘的扰动不敏感的表示。然而,现有的方法大多采用统一的数据增强方案,如统一丢弃边......
  • Reinforcement Learning Charpter 3
    本文参考《ReinforcementLearning:AnIntroduction(2ndEdition)》Sutton 有限MDP有限MDP在RL中一般就是指如下图的交互式学习框架。(为了方便起见,把它当成离散化的过程)其“有限”的特点表现在:state、reward、action三者只有有限个元素其markov性体现在:所以在这种情况下sta......
  • HTML-Learning
    WebLearningHTML标签属性HTML基本结构注释文档声明字符编码设置语言排版语义化标签块级元素和行内元素不常用的标签图片标签相对/绝对路径常见图片格式超链接列表表格常用标签表单HTML字符实体全局属性meta元信息HTML标签规范:小写https://www.w......
  • CSS-Learning
    CSSCSS注释/**/样式表优先级行内:<h1style="color:red;">,属性:值;内部:在head内的style外部:存放在.css文件里CSS风格开发时用展开风格,利于开发上线时用紧凑风格,利于节省体积,加速,(webpack)CSS三大特性布局浮动float定位position:用于指定一个元素在文档......
  • Machine Learning - The Sigmoid Function
    CalculateNodeOutput.TaskYouaregiventhevaluesforw1,w2,b,x1andx2andyoumustcomputetheoutputforthenode.Usethesigmoidastheactivationfunction.InputFormatw1,w2,b,x1andx2ononelineseparatedbyspacesOutputFormatFloatrounded......