首页 > 试题广场 >

假如已知有n个人和m对好友关系(存于数字r)。如果两个人是直

[问答题]

假如已知有n个人和m对好友关系(存于数字r)。如果两个人是直接或间接的好友(好友的好友的好友...),则认为他们属于同一个朋友圈,请写程序求出这n个人里一共有多少个朋友圈。
假如:n = 5,m = 3,r = {{1 , 2} , {2 , 3} , {4 , 5}},表示有5个人,1和2是好友,2和3是好友,4和5是好友,则1、2、3属于一个朋友圈,4、5属于另一个朋友圈,结果为2个朋友圈。
最后请分析所写代码的时间、空间复杂度。评分会参考代码的正确性和效率。
C/C++:
int friends(int n , int m , int* r[]);
Java:
int friends(int n , int m , int[][] r);

推荐
// 简单的并查集应用
int set[10001];

inline int find(int x)           //带路径优化的并查集查找算法
{
    int i , j , r;
    r = x;
    while (set[r] != r)
        r = set[r];
    i = x;
    while (i != r)
    {
        j = set[i];
        set[i] = r;
        i = j;
    }
    return r;
}
inline void merge(int x , int y)     //优化的并查集归并算法
{
    int t = find(x);
    int h = find(y);
    if (t < h) set[h] = t; else set[t] = h;
} 

int friends(int n , int m , int *r[])
{
    int i , count; for (i = 1 ; i <= n ; ++i) //初始化并查集,各点为孤立点,分支数为n 
    set[i] = i; 
    for(i = 0 ; i < m ; ++i) 
        merge(r[i][0] , r[i][1]); 
    count = 0; 
    for(i = 1 ; i <= n ; ++i) { 
        if(set[i] == i) ++count; 
    } 
    return count; 
}
编辑于 2015-02-07 16:33:48 回复(1)
这道题,去年在抖音上也见过,就是用并查集,非常有套路的一道题,回答一下方便学习。
先强势总结一下使用并查集的条件和特点:
1. 肯定是使用集合能解决的问题,因为一些等价条件会变变成几个元素在一个集合,另外几个元素不等价在另外一个集合....。比如好友关系、铁路互通关系。
2. **并查集一定会用到一个和元素数量相同的数组**,如果是元素序号不以0开头,有时候会为了代码方便,使用(元素数量+最小序号)的长度的数组。开始每个元素是一个集合,然后等价关系的便利过程中,会把数组[元素序号]重新赋值。
3. 刚才说的第二点,用程序语言就是:find操作和union操作。
4. find操作和union的写法基本是死的。 

    public int findFriends(int[] find, int i) {
        if (find[i] != i) {
            find[i] = findFriends(find, find[i]);
        }
        return find[i];
    }
    private void union(int[] fathers, int i, int j) {
        fathers[i] = j;
    }
还有类似的问题可以是 城市之间的铁路相连,问有多少城市圈。
然后和leetcode上这一题也很想 https://leetcode-cn.com/explore/interview/card/bytedance/243/array-and-sorting/1036/ 。

import java.util.Arrays;
public class FindCircleNum2 {
    public int friends(int m, int[][] relations) {
        int[] find = new int[m + 1];
        for (int i = 0; i < find.length; i++) {
            find[i] = i;
        }
        Arrays.sort(relations, (o1, o2) -> {
            int nu = o1[0] - o2[0];
            if (nu == 0) {
                return o1[1] - o2[1];
            }
            return nu;
        });
        for (int[] r : relations) {
            int find1 = findFriends(find, r[0]);
            int find2 = findFriends(find, r[1]);
            if (find2 != find1) {
                find[find2] = find1;
                m--;
            }
        }
        return m;
    }
    public int findFriends(int[] find, int i) {
        if (find[i] != i) {
            find[i] = findFriends(find, find[i]);
        }
        return find[i];
    }
    public static void main(String[] args) {
        System.out.println(new FindCircleNum2().friends(7, new int[][]{{4, 6}, {1, 2}, {2, 3}, {4, 5}, {6, 7}}));
    }
}

排序是为了最后生成的find数组,能够更好的看出哪些人在一个集合里(不排序也对)。



发表于 2019-02-26 15:54:48 回复(0)
#include<iostream>
#include<vector>
using namespace std;

//https://blog.csdn.net/fandoudou123/article/details/52936301  https://www.jianshu.com/p/72ea54bb26ab
vector<int>s(6, 0);

int find_root(int x)
{
	int root = x;
	while (root != s[root])//如果掌门人不是自己一直向上查找
	{
		root = s[root];
	}
	int i = x;
	while (i != root)//进行路径优化,减少树的高度为2层,将该路径上所有结点的掌门人都设为root,
	{
		int j = s[i];//保存上一层
		s[i] = root;//将该层的掌门人设为root
		i = j;//当前层赋为上一层
	}
	return root;
}
void find_leader(int x,int y)
{
	int fx = find_root(x);//返回他们的掌门人
	int fy = find_root(y);
	if (fx > fy)s[fx] = fy;//坐标小的为掌门人
	else
		s[fy] = fx;
}


void findfriends(int n, int m, vector<vector<int>>&r,int& count)
{
	for (int i = 1; i <= n; i++)s[i] = i;//每个先初始化下标
	for (int i = 0; i < m; i++)//遍历朋友圈,设置s当前下标的数对应为最上层的朋友root
	{
		find_leader(r[i][0], r[i][1]);
	}
	for (int i = 1; i <= n; i++)
	{
		if (s[i] == i)count++;
	}
}


void main()
{
	vector<vector<int>>r = { { 1, 2 }, { 2, 3 }, { 4, 5 } };
	int n = 5, m = 3;
	int count = 0;
	findfriends(n, m, r,count);
	cout << count << endl;
}

发表于 2019-08-14 16:43:04 回复(0)
int friends(int n , int m , int[][] r) {
        int[] res = new int[n+1];
        int count = 0;
        for (int i = 0; i < m; i++) {
            res[r[i][1]] = -1;
        }
        for (int i = 1; i <= n; i++) {
            if (res[i] == -1) {
                count++;
            }
        }
        return n - count;
    }

发表于 2016-09-20 08:40:29 回复(2)
答案在这里:http://www.cnblogs.com/Lynn-Zhang/p/5610172.html
编辑于 2016-06-24 10:07:54 回复(0)
intset[10001];
 
inlineintfind(intx)           //带路径优化的并查集查找算法
{
    inti , j , r;
    r = x;
    while(set[r] != r)
        r = set[r];
    i = x;
    while(i != r)
    {
        j = set[i];
        set[i] = r;
        i = j;
    }
    returnr;
}
inlinevoidmerge(intx , inty)     //优化的并查集归并算法
{
    intt = find(x);
    inth = find(y);
    if(t < h) set[h] = t; elseset[t] = h;
}
 
intfriends(intn , intm , int*r[])
{
    inti , count; for(i = 1 ; i <= n ; ++i) //初始化并查集,各点为孤立点,分支数为n
    set[i] = i;
    for(i = 0 ; i < m ; ++i)
        merge(r[i][0] , r[i][1]);
    count = 0;
    for(i = 1 ; i <= n ; ++i) {
        if(set[i] == i) ++count;
    }
    returncount;
}

发表于 2015-09-29 17:51:03 回复(0)