資訊專欄INFORMATION COLUMN
摘要：題目鏈接這道題和是一個(gè)思路，一個(gè)初始化為，每次有新的就兩個(gè)節(jié)點(diǎn)，如果兩個(gè)節(jié)點(diǎn)原來不在一個(gè)連通圖里面就減少并且連起來，如果原來就在一個(gè)圖里面就不管。用一個(gè)索引來做，優(yōu)化就是加權(quán)了，每次把大的樹的當(dāng)做，小的樹的作為。
323. Number of Connected Components in an Undirected Graph
題目鏈接：https://leetcode.com/problems...
這道題和numbers of islands II 是一個(gè)思路，一個(gè)count初始化為n，union find每次有新的edge就union兩個(gè)節(jié)點(diǎn)，如果兩個(gè)節(jié)點(diǎn)(u, v)原來不在一個(gè)連通圖里面就減少count并且連起來，如果原來就在一個(gè)圖里面就不管。用一個(gè)索引array來做，union find優(yōu)化就是加權(quán)了，每次把大的樹的root當(dāng)做parent，小的樹的root作為child。
public class Solution {
public int countComponents(int n, int[][] edges) {
// union find
int count = n;
// array to store parent
init(n, edges);
for(int[] edge : edges) {
int root1 = find(edge[0]);
int root2 = find(edge[1]);
if(root1 != root2) {
union(root1, root2);
count--;
}
}
return count;
}
int[] map;
private void init(int n, int[][] edges) {
map = new int[n];
for(int[] edge : edges) {
map[edge[0]] = edge[0];
map[edge[1]] = edge[1];
}
}
private int find(int child) {
while(map[child] != child) child = map[child];
return child;
}
private void union(int child, int parent) {
map[child] = parent;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/66652.html
摘要：算法鏈接學(xué)習(xí)工具，，環(huán)境搭建在小伙伴的推薦下，這個(gè)學(xué)期開始上普林斯頓的算法課。一系列的整數(shù)對代表與相互連接，比如等，每一個(gè)整數(shù)代表了一個(gè)。我覺得這個(gè)可能也是并查集相關(guān)應(yīng)用。這學(xué)期繼續(xù)學(xué)習(xí)深入理解了就能明白了。 《算法》鏈接：1.5 Case Study: Union-Find學(xué)習(xí)工具：mac，java8，eclipse,coursera 環(huán)境搭建在小伙伴的推薦下，這個(gè)學(xué)期開始上普林斯頓...
摘要：感謝您的閱讀如果喜歡這篇文章請點(diǎn)贊。它對我意義重大，它能幫助其他人看到這篇文章。對于更高級的文章，你可以在或上跟隨我。 I’ve worked with Angular.js for a few years and despite the widespread criticism I think this is a fantastic framework. I’ve started w...
Find the number connected component in the undirected graph. Each node in the graph contains a label and a list of its neighbors. (a connected component (or just component) of an undirected graph is a...
閱讀 1927·2021-11-15 11:46
閱讀 1136·2021-10-26 09:49
閱讀 1867·2021-10-14 09:42
閱讀 3413·2021-09-26 09:55
閱讀 862·2019-08-30 13:58
閱讀 1061·2019-08-29 16:40
閱讀 3503·2019-08-26 10:27
閱讀 633·2019-08-23 18:18
