首页 > 编程语言 >算法训练 与1连通的点的个数

算法训练 与1连通的点的个数

时间:2023-07-31 11:45:21浏览次数:38  
标签:pre 连通 temp int fy 个数 public 算法 find

主要思想是并查集,不懂的可以先了解下这个算法再来做题就明白了。
c++实现:

#include<iostream>
#include<vector>
using namespace std;
int f[10000];

//找根节点
int find(int x)
{
    if (f[x] != x)
        f[x] = find(f[x]);
    return f[x];                //不要加else!!!!!!!!! 
}

//连接两个集合
void join(int x, int y)
{
    int a = find(x);
    int b = find(y);
    if (a < b)        //判断两点的根节点大小,合并
        f[b] = a;
    else if (a > b)
        f[a] = b;
}

int main()
{
    int n, m;                        //n:点的个数,m:边
    int temp_1, temp_2,count=0;
    cin >> n >> m;
    //extern vector<int> f(n+1);
    for (int i = 1; i <= n; i++)
    {
        f[i] = i;
    }
    for (int i = 1; i <= m; i++)
    {
        cin >> temp_1 >> temp_2;
        join(temp_1, temp_2);
    }
    //与1同属一个根节点即为两点连通
    int jiedian_1 = find(1);
    for (int i = 1; i <= n; i++)
    {
        if (jiedian_1 == find(i))
            count++;
    }
    cout << count << endl;
    return 0;

以下为java实现代码

import java.util.*;
public class Main {
    static int[] pre;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt();
        pre = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            pre[i] = i;
        }
        for (int i = 0; i < m; i++) {
            int a = sc.nextInt(), b = sc.nextInt();
            join(a, b);
        }
        int traget = find(1), count = 0;
        for (int i = 1; i <= n; i++) {
            int x = find(i);
            if (traget == x) {
                count++;
            }
        }
        System.out.println(count);
    }

    public static void join(int x, int y) {
        int fx = find(x), fy = find(y);
        if (fx > fy) {
            pre[fx] = fy;
        } else {
            pre[fy] = fx;
        }
    }

    public static int find(int x) {
        if (pre[x] != x) {
            pre[x] = find(pre[x]);
        }
        return pre[x];
    }
}

 

标签:pre,连通,temp,int,fy,个数,public,算法,find
From: https://www.cnblogs.com/lcllcl/p/17592918.html

相关文章

  • 强化学习——DQN算法
    1、DQN算法介绍DQN算与sarsa算法和Q-learning算法类似,对于sarsa和Q-learning,我们使用一个Q矩阵,记录所有的state(状态)和action(动作)的价值,不断学习更新,最后使得机器选择在某种状态下,价值最高的action进行行动。但是当state和action的数量特别大的时候,甚至有限情况下不可数时,这时候再......
  • 一个数据丢失惨案
    前言最近,有开发同事联系我反馈一个问题,说开发环境出现了数据丢失的情况,想让DBA帮忙排查一下是不是数据库的问题。我心想大概率是程序bug,不太可能是数据库的问题。不过还是要排查一下才会心安,毕竟对于一个DBA而言,数据丢失无疑是最令人紧张的一件事情。问题排查开始进行排查之前,......
  • 基于内容的个性化推荐算法-电影推荐系统
    之前在博客中介绍了协同过滤算法在电影推荐系统中的应用。今天我将向大家分享另一种常见的推荐算法——基于内容的推荐算法,并使用它来实现一个个性化的电影推荐系统。基于内容的推荐算法原理:基于内容的推荐算法是一种常用的推荐方法,它通过分析电影本身的特征来进行推荐。在电影推荐......
  • 基于标签的个性化推荐算法-电影推荐系统
    之前在博客中介绍了协同过滤算法和基于内容的推荐算法在电影推荐系统中的应用。今天我将向大家介绍另一种常见的推荐算法——基于标签的推荐算法,并使用它来实现一个更加个性化的电影推荐系统。基于标签的推荐算法原理:基于标签的推荐算法是一种利用用户标记信息进行推荐的算法。在电......
  • 点双边双强连通拓展(圆方树)以及一些小技巧
    点双边双强连通拓展以及一些小技巧目录点双边双强连通拓展以及一些小技巧小技巧:1.关于割点:2.关于点双和边双的判断技巧:3.关于自己制造样例的技巧:例题:拓展知识1.广义圆方树:知识点:例题:bzoj3331小技巧:1.关于割点:点双常常存在割点情况,很难搞,每次dfs都很头疼(不知道割点在哪几个连通......
  • [算法学习笔记] 强连通分量
    DFS生成树在介绍强连通分量前,我们先来了解一下DFS生成树。一棵DFS生成树分为树边,前向边,返祖边(一说反向边),横叉边。我们来画图解释一下:在这棵DFS生成树中,黑色为树边,它是在DFS遍历时获得的,红色为返祖边,顾名思义,从儿子指向父亲或祖先。蓝色为横叉边,它是在搜索的时候遇到子树中的节......
  • C#冒泡排序算法
    冒泡排序实现原理冒泡排序是一种简单的排序算法,其原理如下:从待排序的数组的第一个元素开始,依次比较相邻的两个元素。如果前面的元素大于后面的元素(升序排序),则交换这两个元素的位置,使较大的元素“冒泡”到右侧。继续比较下一对相邻元素,重复步骤2,直到遍历到数组的倒数第二......
  • 代码随想录算法训练营第四天| LeetCode 24. 两两交换链表中的节点 19.删除链表的倒
    24.两两交换链表中的节点     卡哥建议:用虚拟头结点,这样会方便很多。 本题链表操作就比较复杂了,建议大家先看视频,视频里我讲解了注意事项,为什么需要temp保存临时节点。   题目链接/文章讲解/视频讲解:https://programmercarl.com/0024.%E4%B8%A4%E4%B8%A4%E4%BA%......
  • 文心一言 VS 讯飞星火 VS chatgpt (68)-- 算法导论6.5 7题
    文心一言VS讯飞星火VSchatgpt(68)--算法导论6.57题七、试说明如何使用优先队列来实现一个先进先出队列,以及如何使用优先队列来实现栈(队列和栈的定义见10.1节。)文心一言:优先队列是一种数据结构,其中每个元素都有一个关联的优先级或权值。在优先队列中,元素按照它们的优先级被......
  • JavaScript学习 -- 对称加密算法DES
    在现代的互联网时代,数据安全性备受关注。为了保护敏感数据的机密性,对称加密算法是一种常用的方法。在JavaScript中,DES(DataEncryptionStandard)是一种常用的对称加密算法。本篇博客将为您展示如何在JavaScript中使用DES算法进行加密和解密,并提供一个实际的例子。首先,我们需要使用Cr......