首页 > 试题广场 >

计算朋友圈

[编程题]计算朋友圈
  • 热度指数:201 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
假设有N个用户,其中有些人是朋友,有些则不是。A和B是朋友,B和C是朋友,这样ABC就是一个朋友圈,请计算给定的朋友关系的朋友圈数。
给定一个 N * N 的矩阵 M,表示用户之间的朋友关系。如果M[i][j] = 1,表示已知第 i 个和 j 个人互为朋友关系,否则为不知道。你必须输出所有用户中的已知的朋友圈总数。


输入描述:
第一行输入为表示用户数N
第2到1+N行表示朋友之间关系,如果值为1表示有朋友关系


输出描述:
输出朋友圈数
示例1

输入

3
1,1,0
1,1,0
0,0,1

输出

2

说明

第0个用户和第1个用户组成一个朋友圈,第2个用户组成一个朋友圈
示例2

输入

3
1,1,0
1,1,1
0,1,1

输出

1

说明

第0,1,2个用户组成了一个朋友圈

备注:
如果M[i][j] = 1 那么 如果M[j][i] = 1,用户自己和自己肯定是朋友关系即M[i][i]=1
用户数量不超过10000
并查集裸题  写得啰里啰嗦....

import java.io.*;
import java.util.*;

public class Main{
    
    
    public static void main(String[] args)throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[][] arr = new int[n][n];
        for(int i=0;i<n;++i){
            String[] arg = br.readLine().split(",");
            for(int j=0;j<n;++j){
                arr[i][j] = Integer.parseInt(arg[j]);
            }
        }
        
        int[] f = new int[n];
        for(int i=0;i<n;++i){
            f[i]=i;
        }
        
        for(int i=0;i<n;++i){
            for(int j=0;j<n;++j){
                if(arr[i][j] == 1){
                    union(f,i,j);
                }
            }
        }
        int ans =0;
        for(int i=0;i<n;++i){
            if(f[i]==i){
                ans++;
            }
        }
        System.out.println(ans);
    }
    
    public static int find(int[] f, int a){
        if(f[a]==a){
            return a;
        }
        return f[a] = find(f,f[a]);
    }
    public static void union(int[] f, int a,int b){
        int fa = find(f,a);
        int fb = find(f,b);
        f[fa]=fb;
    }
}


发表于 2021-02-16 23:41:53 回复(0)

从每个未访问过的节点(用户)出发,进行 dfs 搜索。

dfs 的次数,就是朋友圈的数目。

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
public class Main {
  public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    int n = scanner.nextInt();
    String[][] relations = new String[n][n];
    for (int i = 0; i < n; i++) {
      relations[i] = scanner.next().split(",");
    }
    scanner.close();
    System.out.println(friendCircle(relations));
  }
  private static int friendCircle(String[][] relations) {
    int n = relations.length;
    // graph[i] -> 用户 i 的所有朋友
    Set[] graph = new HashSet[n];
    for (int i = 0; i < n; i++) {
      graph[i] = new HashSet();
      for (int j = 0; j < n; j++) {
        int relation = Integer.parseInt(relations[i][j]);
        if (relation == 1) {
          graph[i].add(j);
        }
      }
    }
    int ans = 0;
    boolean[] visited = new boolean[n];
    for (int i = 0; i < n; i++) {
      if (!visited[i]) {
        ans++;
        dfs(graph, i, visited);
      }
    }
    return ans;
  }
  private static void dfs(Set[] graph, int cur, boolean[] visited) {
    visited[cur] = true;
    for (int next : graph[cur]) {
      if (!visited[next]) {
        dfs(graph, next, visited);
      }
    }
  }
}
编辑于 2022-03-30 22:07:00 回复(0)

用一个set集合存储朋友圈列表。通过&与操作判断是否存在朋友关系,通过|或操作进行朋友圈融合,set集合剩下多少个元素代表有多少个朋友圈

  public static void main(String[] args) {     Scanner in = new Scanner(System.in);     // 注意 hasNext 和 hasNextLine 的区别     int arrLen = Integer.parseInt(in.nextLine());     Set<Integer> binaryIntFC = new HashSet<>();     for (int i = 0; i < arrLen; i++) {       String line = in.nextLine();       String[] split = line.split(",");       StringBuilder sb = new StringBuilder();       for (int j = 0; j < split.length; j++) {         sb.append(Integer.parseInt(split[j]));       }       binaryIntFC.add(Integer.parseInt(sb.toString(), 2));     }     Set<Integer> friendCircles = new HashSet<>();     for (Integer binaryInt : binaryIntFC) {       if (friendCircles.size() == 0) {         friendCircles.add(binaryInt);         continue;       }       // 判断当前set值与目标setlist是否有朋友关系,决定是否进行融合       boolean isFriend = false;       for (Integer targetIntSet : friendCircles) {         if ((targetIntSet & binaryInt) > 0) { // 有朋友关系,进行融合           int mergeInt = targetIntSet | binaryInt;           friendCircles.remove(targetIntSet);           friendCircles.add(mergeInt);           isFriend = true;           break;         }       }       if (!isFriend) { // 没有朋友关系,直接加入到目标setlist中,成为一个新的朋友圈         friendCircles.add(binaryInt);       }     }     System.out.println(friendCircles.size());   }

编辑于 2023-06-15 12:02:23 回复(0)
import java.util.*;
public class Main {

        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            String s = sc.nextLine();
            int n = Integer.parseInt(s);
            UnionFindSet ufs = new UnionFindSet(n);
            int res = n;
            for (int i = 0; i < n; i++) {
                s = sc.nextLine();
                String[] ss = s.split(",");
                for (int j = 0; j < i; j++) {
                    int cur = Integer.parseInt(ss[j]);
                    if (cur == 1) {
                        res = ufs.union(i, j);
                    }
                }
            }
            sc.close();
            System.out.println(res);
        }

        static class UnionFindSet {
            int[] parent;
            int size;

            UnionFindSet(int n) {
                this.parent = new int[n];
                for (int i = 0; i < n; i++) {
                    parent[i] = i;
                }
                this.size = n;
            }

            int find(int n) {
                if (n == parent[n]) {
                    return n;
                }
                int r = find(parent[n]);
                parent[n] = r;
                return r;
            }

            int union(int n1, int n2) {
                int r1 = find(n1), r2 = find(n2);
                if (r1 == r2) {
                    return size;
                } else {
                    if (r1 < r2) {
                        parent[r2] = r1;
                    } else {
                        parent[r1] = r2;
                    }
                    return --size;
                }
            }

        }

    }

发表于 2022-03-09 17:14:52 回复(0)
#include <iostream>
#include <vector>
using namespace std;

// 并查集
class UnionFind
{
public:
    UnionFind(size_t n)
        :_v(n, -1)
    {}
    
    int FindIdx(int index)
    {
        while(_v[index] >= 0)
        {
            index = _v[index];
        }
        return index;
    }
    
    bool Merge(int idx1, int idx2)
    {
        int root1 = FindIdx(idx1);
        int root2 = FindIdx(idx2);
        if(root1 == root2)
            return false;
        _v[root1] += _v[root2];
        _v[root2] = root1;
        return true;
    }
    
    size_t Count() const
    {
        size_t count = 0;
        for(const auto& e : _v)
        {
            if(e < 0)
                count++;
        }
        return count;
    }
    
    vector<int> _v;
};

int main()
{
    int n;
    while(cin >> n)
    {
        vector<vector<int>> v(n, vector<int>(n, 0));
        UnionFind uni(n);
        for(int i = 0; i < n; i++)
        {
            string str;
            cin >> str;
            for(int j = 0, k = 0; j < n; j++, k += 2)
                v[i][j] = str[k] - '0';
        }
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < n; j++)
            {
                if(i == j)
                    continue;
                if (v[i][j] == 1)
                    uni.Merge(i, j);
            }
        }
        
        cout << uni.Count() << endl;
        
    }
    return 0;
}

编辑于 2022-03-13 10:19:11 回复(0)
本来是想找并查集练习的,
但没找到更好的题目,
就先用这道限java的试一试.
数组并查集, 见谅见谅
#include <iostream>

bool temp[10001][10001];
int pre[10001]; //前驱

int unionsearch(int root) {
    int son, tmp;
    son = root;
    while (root != pre[root]) root = pre[root]; //寻找最终节点
    while (son != root) { //路径压缩(递归)
        tmp = pre[son];
        pre[son] = root; //root是最终节点 
        son = tmp; //向前寻找 
    }
    return root;
}

int main() {
    int a, b;
    int root1, root2;
    int total;
    char c;
    std::cin>>a;
    total = a;
    for(int i = 0; i < a; i++){
        pre[i] = i;
        for(int j = 0; j < a; j++){
            std::cin>>b;
            if(b == 1) temp[i][j] = true;
            if(j != a-1) std::cin>>c;
        }
    }

    for(int i = 0; i < a; i++){
        for(int j = 0; j < i / 2 + 1; j++){
            if(temp[i][j] == temp[j][i] && j!=i && temp[i][j]){
                root1 = unionsearch(i);
                root2 = unionsearch(j);
                if(root1 != root2){
                    pre[root1] = root2;
                    total--;
                }
            }
        }
    }
    std::cout<<total;
    return 0;
}
发表于 2021-03-25 21:33:54 回复(0)
并查集
import java.util.Scanner;

/**
 * @author Frank KONG
 * @version 1.0
 * @date 2021/2/24 10:47
 */
public class Main {

    public static void main(String[] args) {
        int n;
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        int[][] graph = new int[n][n];

        for(int i = 0; i < n; i++){
            String s = scanner.next();
            String[] split = s.split(",");
            for(int j = 0; j < n; j++){
                graph[i][j] = Integer.valueOf(split[j]);
            }
        }

        //0~n-1编号
        int[] parent = new int[n];
        for(int i = 0; i < n; i++){
            parent[i] = i;
        }

        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if(graph[i][j] == 1){
                    //有关系,加入集合
                    int parentI = find(parent, i);
                    int parentJ = find(parent, j);
                    if(parentI != parentJ){
                        parent[parentI] = parentJ;
                    }
                }
            }
        }

        //查看有几个集合
        int res = 0;
        for(int i = 0; i < n; i++){
            if(parent[i] == i) res++;
        }
        System.out.println(res);
    }

    public static int find(int[] parent, int index){
        if(parent[index] != index){
            index = parent[index];
        }
        return index;
    }

}


发表于 2021-02-24 11:00:16 回复(2)