计算朋友圈

从每个未访问过的节点(用户)出发，进行 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);
      }
    }
  }
}

用一个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());
  }

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;
                }
            }

        }

    }

#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;
}