28 if (num_nodes == old_num_nodes) {

29 return;

30 }

31 CHECK_GE(num_nodes, 0) << "Number of nodes overflowed the `int` type.";

32 CHECK_GT(num_nodes, old_num_nodes);

33

34

35 parent_.resize(num_nodes);

36 std::iota(parent_.begin() + old_num_nodes, parent_.end(), old_num_nodes);

37

38 component_size_.resize(num_nodes, 1);

39

40 rank_.resize(num_nodes);

41

42 num_components_ += num_nodes - old_num_nodes;

43}

46 DCHECK_GE(node, 0);

48

49

50 int root = parent_[node];

51 while (parent_[root] != root) {

52 root = parent_[root];

53 }

54

55

56 while (node != root) {

57 const int prev_parent = parent_[node];

58 parent_[node] = root;

59 node = prev_parent;

60 }

61 return root;

62}

66 if (num_nodes != num_nodes_at_last_get_roots_call_) {

67

68

69

70 const int previous_num_roots = roots_.size();

71 roots_.resize(previous_num_roots + num_nodes -

72 num_nodes_at_last_get_roots_call_);

73 std::iota(roots_.begin() + previous_num_roots, roots_.end(),

74 num_nodes_at_last_get_roots_call_);

75 }

76

77

78

79

81 &roots_, [&](const int node) { return node != FindRoot(node); });

82

83 num_nodes_at_last_get_roots_call_ = num_nodes;

84 return roots_;

85}

88

89 const int min_num_nodes = std::max(node1, node2) + 1;

92 }

93

94

97

98

99 if (root1 == root2) {

100 return false;

101 }

102

103 DCHECK_GE(num_components_, 2);

104 --num_components_;

105

106 const int component_size = component_size_[root1] + component_size_[root2];

107

108

109

110

111 if (rank_[root1] > rank_[root2]) {

112 parent_[root2] = root1;

113 component_size_[root1] = component_size;

114 } else {

115 parent_[root1] = root2;

116 component_size_[root2] = component_size;

117

118 if (rank_[root1] == rank_[root2]) {

119 ++rank_[root2];

120 }

121 }

122 return true;

123}

128 return false;

129 }

131}

135 return 0;

136 }

137 return component_size_[FindRoot(node)];

138}

142 int current_component = 0;

144 int& root_component = component_ids[FindRoot(node)];

145 if (root_component < 0) {

146

147 root_component = current_component;

148 ++current_component;

149 }

150 component_ids[node] = root_component;

151 }

152 return component_ids;

153}

bool Connected(int node1, int node2)

Definition connected_components.cc:125

int GetSize(int node)

Definition connected_components.cc:133

bool AddEdge(int node1, int node2)

Definition connected_components.cc:87

int GetNumberOfNodes() const

void SetNumberOfNodes(int num_nodes)

Definition connected_components.cc:26

std::vector< int > GetComponentIds()

Definition connected_components.cc:140

const std::vector< int > & GetComponentRoots()

Definition connected_components.cc:64

int FindRoot(int node)

Definition connected_components.cc:45

void STLEraseAllFromSequenceIf(T *v, P pred)