有道关于图的OA题没做出来，undirected graphs求unreachable nodes个数，求大神帮助！

有以下三种sample case，无向图转成有向图之后求解unreachable nodes的最少个数。


有类似的leetcode题吗？或者有什么思路？懂BFS和DFS，会不会是通过判断图里有没有cycle来求解？求大神帮忙！

image.png

image.png

image.png

不需要这么麻烦，直接在无向图里算入度，
答案就是“入度为1的node个数减1”加上“入度为0的node个数”
第一项减1是因为可以用一个"入度为1的node"作为终点
没有这种node，第一项就是0

这道题你首先求连通分量，然后看这个连通分量里的边数是不是少于点数，少了就加一。本质上就是把一个连通分量转换为树，如果连通分量里有环，就可以把环中的点当作根，来防止unreachable

je4ever 发表于 2024-01-11 10:58:30
谢谢你的分享！
虽然我不是很理解你的第二句话，但是我可不可以把第一句话当成完整的解题思路。如果没有环，边数就会少于点数，那这个分量就会有一个node是unre

有环的话，边数是大于等于点数，所以你只要看所有连通分量是否满足这个条件就好了

hur 发表于 2024-1-11 11:56
这道题你首先求连通分量，然后看这个连通分量里的边数是不是少于点数，少了就加一。本质上就是把一个连通分 ...

谢谢你的分享！
虽然我不是很理解你的第二句话，但是我可不可以把第一句话当成完整的解题思路。如果没有环，边数就会少于点数，那这个分量就会有一个node是unreachable的，就加一。
照第一句话的思路的话，第二句话，如果有环，那边数应该是等于点数的对吧？代码里需要转换成树吗？
不知道你的两句话我的理解对不对？

vincent_great 发表于 2024-1-14 00:19
不需要这么麻烦，直接在无向图里算入度，
答案就是“入度为1的node个数减1”加上“入度为0的node个数”
...

请问self-loop的入度是不是不应该算？

lz这题会有self- loop吗？

jenny20202020 发表于 2024-2-15 09:56
lz这题会有self- loop吗？

会有。
这道题我目前的解法就是用union set find算法，如果一个union set里有loop，那这个union set里就不会有unreachable node，因为就像公路如果有一个环连接所有公路，那每个node都是可以到达的。

贴上我的代码仅供参考。

1.     public int countMinimunUnreachableWarehouses(int warehouseNodes, int[][] edges) {
   
2. 
   
3.         int[] parent = new int[warehouseNodes + 1];
   
4.         Arrays.fill(parent, -1);
   
5. 
   
6.         Set<Integer> cycleSet = new HashSet<>();
   
7.         for(int i = 0; i < edges.length; i++) {
   
8.             int f = edges[i][0];
   
9.             int t = edges[i][1];
   
10. 
    
11.             int fset = find(parent, f);
    
12.             int tset = find(parent, t);
    
13.             if(fset == tset)
    
14.                 cycleSet.add(fset);
    
15.             else
    
16.                 parent[fset] = tset;
    
17.         }
    
18. 
    
19.         int count = 0;
    
20.         Set<Integer> visited = new HashSet<>();
    
21.         for(int i = 1; i < warehouseNodes + 1; i++) {
    
22.             int root = find(parent, i);
    
23.             if(visited.contains(root))
    
24.                 continue;
    
25.             else {
    
26.                 visited.add(root);
    
27.                 if(!cycleSet.contains(root))
    
28.                     count++;
    
29.             }
    
30.         }
    
31. 
    
32.         return count;
    
33.     }
    
34. 
    
35.     private int find(int[] parent, int n) {
    
36.         if(parent[n] == -1)
    
37.             return n;
    
38.         return find(parent, parent[n]);
    
39.     }
    

复制代码