If you have a fixed graph where the node are dense integers, use GetConnectedComponents(): it's very fast and uses little memory.
If you have a more dynamic scenario where you want to incrementally add nodes or edges and query the connectivity between them, use the [Dense]ConnectedComponentsFinder class, which uses the union-find algorithm aka disjoint sets: https://en.wikipedia.org/wiki/Disjoint-set_data_structure.
[[["Easy to understand","easyToUnderstand","thumb-up"],["Solved my problem","solvedMyProblem","thumb-up"],["Other","otherUp","thumb-up"]],[["Missing the information I need","missingTheInformationINeed","thumb-down"],["Too complicated / too many steps","tooComplicatedTooManySteps","thumb-down"],["Out of date","outOfDate","thumb-down"],["Samples / code issue","samplesCodeIssue","thumb-down"],["Other","otherDown","thumb-down"]],["Last updated 2024-08-06 UTC."],[[["\u003cp\u003eThis documentation explains how to find connected components in undirected graphs using tools provided by Or-Tools.\u003c/p\u003e\n"],["\u003cp\u003eFor graphs with dense integer nodes, \u003ccode\u003eGetConnectedComponents()\u003c/code\u003e offers a fast and memory-efficient solution.\u003c/p\u003e\n"],["\u003cp\u003eFor dynamic scenarios with incremental node/edge additions and connectivity queries, use the \u003ccode\u003e[Dense]ConnectedComponentsFinder\u003c/code\u003e class, which leverages the union-find algorithm.\u003c/p\u003e\n"],["\u003cp\u003eTwo classes, \u003ccode\u003eConnectedComponentsFinder\u003c/code\u003e and \u003ccode\u003eDenseConnectedComponentsFinder\u003c/code\u003e, are available for different use cases and can be further explored through the provided links.\u003c/p\u003e\n"]]],["The core content details two methods for finding connected components in an undirected graph. `GetConnectedComponents()` is recommended for static graphs with dense integer nodes, offering speed and efficiency. For dynamic scenarios involving incremental changes, `DenseConnectedComponentsFinder` is suggested. It employs the union-find algorithm. Two classes, `ConnectedComponentsFinder` and `DenseConnectedComponentsFinder`, are provided for these respective approaches. Both are designed to determine the connected components within a given graph structure.\n"],null,["# connected_components\n\nC++ Reference: connected_components\n===================================\n\n\nNote: This documentation is automatically generated.\nFinds the connected components in an undirected graph: \u003chttps://en.wikipedia.org/wiki/Connected_component_(graph_theory\u003e) \n\nIf you have a fixed graph where the node are dense integers, use GetConnectedComponents(): it's very fast and uses little memory. \n\nIf you have a more dynamic scenario where you want to incrementally add nodes or edges and query the connectivity between them, use the \\[Dense\\]ConnectedComponentsFinder class, which uses the union-find algorithm aka disjoint sets: \u003chttps://en.wikipedia.org/wiki/Disjoint-set_data_structure\u003e.\n\n| Classes ------- ||\n|---------------------------------------------------------------------------------------------------------------------|---|\n| [ConnectedComponentsFinder](/optimization/reference/graph/connected_components/ConnectedComponentsFinder) |\n| [DenseConnectedComponentsFinder](/optimization/reference/graph/connected_components/DenseConnectedComponentsFinder) |"]]