FilesExpand file tree

 master

/

Connecting Graph II.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

88 lines (74 loc) · 2.13 KB

 master

/

Connecting Graph II.java

Copy path

Top

File metadata and controls

• Code
• Blame

88 lines (74 loc) · 2.13 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

M

1520320968

tags: Union Find

Lint还不能跑, 全部按照题意和答案document的.

```

/*

LintCode:

Given n nodes in a graph labeled from 1 to n. There is no edges in the graph at beginning.

You need to support the following method:

1. connect(a, b), add an edge to connect node a and node b.

2. query(a), Returns the number of connected component nodes which include node a.

Example

5 // n = 5

query(1) return 1

connect(1, 2)

query(1) return 2

connect(2, 4)

query(1) return 3

connect(1, 4)

query(1) return 3

*/

/**

Thoughts:

No chance to run on LintCode.

*/

public class ConnectingGraph {

// Placeholder for all the UninFind relationships

private int[] father = null;

// Stores the number of union elements connected from downstream to each individual node

private int[] size = null;

/**

Initialize one element to each individual union; size will be 1 for all unions as well.

*/

public ConnectingGraph(int n) {

father = new int[n + 1];

size = new int[n + 1];

for (int i = 1; i <= n; i++) {

father[i] = i;

size[i] = 1;

}

}

/**

Union function.

Find the root father, if not the same, union them together.

*/

public void connect(int a, int b) {

int rootA = find(a);

int rootB = find(b);

if (rootA != rootB) {

parent[a] = rootB; // doesn't mater which assigns to which one.

// Merge union of A into the union of B, so unionB should grow.

size[rootB] += size[rootA]

}

}

/**

Returns the number of connected component nodes which include node a.

*/

public boolean query(int x) {

int rootX = find(x);

return size[rootX];

}

/*

Find function: find the root parent as the head for entire union.

If found parent as itself, return it.

Otherwise, recursively look for father and assign the result eventually.

*/

private int find(int x) {

if (father[x] == x) {

return x; // x is the root parent, return itself.

}

return father[x] = find(father[x]);

}

}

```