正文

求解朋友关系中的朋友圈数量

赵弘添  赵弘添  2022-08-30  670

关键词：

问题描述：给出10w条人和人之间的朋友关系，求出这些朋友关系中有多少个朋友圈

样例A-B、B-C、D-E、E-F ，这四对关系中存在2个朋友圈

解题思路：并查集，而题目只需要求出朋友圈数量，并不需要求出各朋友圈，所以该并查集的实现也可以非常简单。

A-B,就把father[B] = A，处理每条朋友关系即可得到结果。

而关于并查集的介绍，已有很多博文有所阐述，这里就不啰嗦了。

如下给出实现的并查集

Python实现

class WeightedUF():  
    fatherid=[]  
    sz=[]  
    count=0  
    def __init__(self,n):  
        self.count=n  
        self.fatherid=[i for i in range(n)]  
        self.sz=[0 for i in range(n)]  
    def getcount(self):  
        return self.count  
    def connected(self,p,q):  
        return self.find(p)==self.find(q)  
    def find(self,p):  
        while p !=self.fatherid[p]:  
            p=self.fatherid[p]  
        return p  
    def pathcompressionfind(self,p):  
        if p==self.fatherid[p]:  
            return p  
        else:  
            self.fatherid[p]=self.pathcompressionfind(self.fatherid[p])  
            return self.fatherid[p]  
    def union(self,p,q):  
        i=self.find(p)  
        j=self.find(q)  
        if i==j:  
            return   
        if self.sz[i]<self.sz[j]:  
            self.fatherid[i]=j  
            self.sz[j]+=self.sz[i]  
        else:  
            self.fatherid[j]=i  
            self.sz[i]+=self.sz[j]  
        self.count-=1

Java实现

public class WeightUF {
    int[] fatherid ;
    int[] sz;
    int count = 0;
    public WeightUF(int n){
        this.count = n;
        this.fatherid = new int[n];
        this.sz = new int[n];
        for(int i=0;i<n;i++){
            fatherid[i] = i;
            sz[i] = 0;
        }
    }
    public int getCount(){
        return count;
    }
    public boolean connected(int p,int q){
        return find(p) == find(q);
    }
    public int find(int p){
        while (p != fatherid[p]){
            p = fatherid[p];
        }
        return p;
    }
    public int pathcompressionfind(int p){
        if(p == fatherid[p]){
            return p;
        }
        else{
            fatherid[p] = pathcompressionfind(p);
            return fatherid[p];
        }
    }
    public void union(int p,int q){
        int i = find(p);
        int j = find(q);
        if(i == j){
            return;
        }
        if(sz[i] < sz[j]){
            fatherid[i] = j;
            sz[j] += sz[i];
        }
        else{
            fatherid[j] = i;
            sz[i] += sz[j];
        }
        count -= 1;
    }
}

测试样例（java）

public static void main(String[] args) {
        WeightUF weightUF = new WeightUF(10);
        weightUF.union(9,2);
        weightUF.union(9,3);
        weightUF.union(1,2);
        weightUF.union(5,4);
        System.out.println(weightUF.getCount());
        System.out.println(weightUF.connected(9,4));
        System.out.println(weightUF.connected(9,5));
    }

朋友圈的人脉关系的算法

...友 2、二度人脉：双方有一个以上共同的好友，这时朋友网可以计算出你们有几个共同的好友并且呈现数字给你。你们的关系是：你->朋友->陌生人 3、三度人脉：即你朋友的朋友的朋友就是这个陌生人。你们的关系是... 查看详情

547.朋友圈(代码片段)

班上有 N 名学生。其中有些人是朋友，有些则不是。他们的友谊具有是传递性。如果已知A是B 的朋友，B是C 的朋友，那么我们可以认为A也是C 的朋友。所谓的朋友圈，是指所有朋友的集合。给定一个 N*N ... 查看详情

leetcode朋友圈(代码片段)

题目1526：朋友圈

题目1526：朋友圈时间限制：1秒内存限制：128兆特殊判题：否提交：1675解决：514题目描述：假如已知有n个人和m对好友关系（存于数字r）。如果两个人是直接或间接的好友（好友的好友的好友...），则认为他们属于同一个朋友圈... 查看详情

“朋友仅展示最近三天的朋友圈”的背后

650)this.width=650;"src="%7B4111.jpg%7D"/>有一次闲来无事翻看一个朋友的朋友圈，结果除了封面没有任何动态，只有一条灰杠和一句“朋友仅展示最近三天的朋友圈”。我突然就吓了一跳，以为是她屏蔽我了，想想不可能啊，我们的关系... 查看详情

并查集的应用

...查询问题。常常在使用中以森林来表示。应用若某个朋友圈过于庞大，要判断两个人是否是在一个朋友圈，确实还很不容易，给出某个朋友关系图，求任意给出的两个人是否在一个朋友圈。规定：x和y是朋友，y和z是朋友，... 查看详情

并查集的应用

[8.16考试]小皮的疑惑(代码片段)

...系，那么A和C之间也会有一定联系。小皮喜欢研究他人的朋友圈,在他看来不满足上述关系的朋友圈都是不正常的朋友圈,可是人多起来关系也摸不清,请你来帮忙写一个程序检查该朋友圈是否正常.假设一个朋友圈有N个人，M组关系... 查看详情

微信朋友圈视频链接中的视频怎么下载到电脑?

【操作方法及原理】：将视频链接发送到电脑，使用工具下载链接中的视频到自己电脑。http://jingyan.baidu.com/article/48b37f8d3fd09a1a6464882d.html 维棠将视频链接中的视频进行下载查看详情

微信怎么发朋友圈让图片并排3张呢

微信怎么发朋友圈让图片并排3张呢在朋友圈右上角点击小相机，如往常发布动态相同操作，然后选中三张要发送的图片，这时候千万记得不要配文字！这样发送出去就是并排的三张了。微信朋友圈指的是腾讯微信上的一个社交... 查看详情

[小米]并查集

...的好友（好友的好友的好友…）。则觉得他们属于同一个朋友圈，请敲代码求出这n个人里一共同拥有多少个朋友圈。假如：n=5。m=3，r={{1,2},{2,3},{4,5}}，表示有5个人。1和2是好友，2和3是好友，4和5是好友。则1、2、3属于一个朋友... 查看详情

社交网络中的朋友关系

】社交网络中的朋友关系【英文标题】：FriendRelationshipsinaSocialNetwork【发布时间】：2010-12-0404:08:27【问题描述】：我认为与其维护一个包含我网络上所有用户的关系列表的朋友关系表，不如为网络上的每个用户创建一个单独的关... 查看详情

朋友圈广告投放！在哪设置白名单

朋友圈广告投放，设置白名单的具体步骤如下：我们需要准备的材料分别是：电脑、百度浏览器。1、首先我们打开百度浏览器，点击搜索“微信公众平台”。2、然后我们在弹出来的窗口中点击打开“微信公众平台”，登录自己... 查看详情

l1-020.帅到没朋友

L1-020.帅到没朋友时间限制200ms内存限制65536kB代码长度限制8000B判题程序Standard作者陈越当芸芸众生忙着在朋友圈中发照片的时候，总有一些人因为太帅而没有朋友。本题就要求你找出那些帅到没有朋友的人。输入格式：输入第一... 查看详情

l1-20帅到没朋友

l1-020.帅到没朋友

L1-020.帅到没朋友当芸芸众生忙着在朋友圈中发照片的时候，总有一些人因为太帅而没有朋友。本题就要求你找出那些帅到没有朋友的人。输入格式：输入第一行给出一个正整数N（<=100），是已知朋友圈的个数；随后N行，每行... 查看详情

微信朋友圈测试用例

这里写目录标题功能测试发朋友圈只发送文本只发送图片只发送视频以上模式搭配使用，是否可以正常使用所在的位置谁可以看提醒谁看是否同步到QQ空间发送浏览朋友圈文本查看图片查看视频查看分享朋友圈点赞评论删除... 查看详情

微信输入几个字，就能查看好友朋友圈所有动态！你不会不知道吧

...使用人数最多的社交工具，很多小伙伴都喜欢在微信上交朋友。但对方毕竟是陌生人，所以还是要认真了解一下，而查看对方朋友圈就是最快的了解方式。其实微信只要输入几个字，就能查看好友4年内所有朋友圈内容。不信？... 查看详情