<
查看: 1752| 回复: 7
收起左侧

[树/链表/图] 有道关于图的OA题没做出来,undirected graphs求unreachable nodes个数,求大神帮助!

je4ever | 显示全部楼层
本楼:   👍  0
0%
0%
0   👎
全局:   6
60%
40%
4

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
本帖最后由 je4ever 于 2024-1-11 09:20 编辑

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


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


image.png

image.png



image.png

image.png



image.png

image.png

评分

参与人数 2大米 +3 收起 理由
sqz0914 + 1 给你点个赞!
14417335 + 2 给你点个赞!

查看全部评分


上一篇:刷题求助:以前自己动脑写出的题,过段时间写不出来了
下一篇:开帖记录一下刷题
vincent_great 2024-1-14 13:19:55 | 显示全部楼层
本楼:   👍  2
100%
0%
0   👎
全局:   312
97%
3%
11
本帖最后由 vincent_great 于 2024-1-14 05:22 编辑

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

使用道具 举报

hur 2024-1-12 00:56:15 来自APP | 显示全部楼层
本楼:   👍  2
100%
0%
0   👎
全局:   6
100%
0%
0
这道题你首先求连通分量,然后看这个连通分量里的边数是不是少于点数,少了就加一。本质上就是把一个连通分量转换为树,如果连通分量里有环,就可以把环中的点当作根,来防止unreachable

评分

参与人数 1大米 +1 收起 理由
14417335 + 1 给你点个赞!

查看全部评分

回复

使用道具 举报

hur 2024-1-13 03:33:58 来自APP | 显示全部楼层
本楼:   👍  1
100%
0%
0   👎
全局:   6
100%
0%
0
je4ever 发表于 2024-01-11 10:58:30
谢谢你的分享!
虽然我不是很理解你的第二句话,但是我可不可以把第一句话当成完整的解题思路。如果没有环,边数就会少于点数,那这个分量就会有一个node是unre
有环的话,边数是大于等于点数,所以你只要看所有连通分量是否满足这个条件就好了
回复

使用道具 举报

 楼主| je4ever 2024-1-12 02:58:30 | 显示全部楼层
本楼:   👍  0
0%
0%
0   👎
全局:   6
60%
40%
4
hur 发表于 2024-1-11 11:56
这道题你首先求连通分量,然后看这个连通分量里的边数是不是少于点数,少了就加一。本质上就是把一个连通分 ...

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

评分

参与人数 1大米 +1 收起 理由
14417335 + 1 给你点个赞!

查看全部评分

回复

使用道具 举报

jenny20202020 2024-2-15 22:54:41 | 显示全部楼层
本楼:   👍  0
0%
0%
0   👎
全局:   5
36%
64%
9
vincent_great 发表于 2024-1-14 00:19
不需要这么麻烦,直接在无向图里算入度,
答案就是“入度为1的node个数减1”加上“入度为0的node个数”
...

请问self-loop的入度是不是不应该算?
回复

使用道具 举报

jenny20202020 2024-2-15 22:56:02 | 显示全部楼层
本楼:   👍  0
0%
0%
0   👎
全局:   5
36%
64%
9
lz这题会有self- loop吗?
回复

使用道具 举报

 楼主| je4ever 2024-2-16 20:31:16 | 显示全部楼层
本楼:   👍  0
0%
0%
0   👎
全局:   6
60%
40%
4
本帖最后由 je4ever 于 2024-2-16 07:33 编辑
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.         int[] parent = new int[warehouseNodes + 1];
  3.         Arrays.fill(parent, -1);

  4.         Set<Integer> cycleSet = new HashSet<>();
  5.         for(int i = 0; i < edges.length; i++) {
  6.             int f = edges[i][0];
  7.             int t = edges[i][1];

  8.             int fset = find(parent, f);
  9.             int tset = find(parent, t);
  10.             if(fset == tset)
  11.                 cycleSet.add(fset);
  12.             else
  13.                 parent[fset] = tset;
  14.         }

  15.         int count = 0;
  16.         Set<Integer> visited = new HashSet<>();
  17.         for(int i = 1; i < warehouseNodes + 1; i++) {
  18.             int root = find(parent, i);
  19.             if(visited.contains(root))
  20.                 continue;
  21.             else {
  22.                 visited.add(root);
  23.                 if(!cycleSet.contains(root))
  24.                     count++;
  25.             }
  26.         }

  27.         return count;
  28.     }

  29.     private int find(int[] parent, int n) {
  30.         if(parent[n] == -1)
  31.             return n;
  32.         return find(parent, parent[n]);
  33.     }
复制代码
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

Advertisement
>
快速回复 返回顶部 返回列表