注册一亩三分地论坛,查看更多干货!
您需要 登录 才可以下载或查看附件。没有帐号?注册账号 
x
我收到的是180min版本的老题,, 地里随便一搜就有解法。
具体解法第一题用bfs/dfs/union-find, 第二题先按照长度排序然后DP, 3hrs足够了, 写完第二天收到HR消息, 之后约电面和onsite。
写一下第一题相对不太常见的union-find解法, 攒个人品。
初始化int[] arr存每个节点i的root,并让每个i指向自己: arr[i]=i。然后对一条边(i, j),调用linkroot(i, j)。最后返回arr中有多少个指向自己的i。下边是union-find的两个操作函数。
|