{"id":15426,"date":"2023-04-02T12:37:33","date_gmt":"2023-04-02T09:07:33","guid":{"rendered":"https:\/\/nabfollower.com\/blog\/disjoint-set-union-heuristics-2e82\/"},"modified":"2023-04-02T12:37:33","modified_gmt":"2023-04-02T09:07:33","slug":"disjoint-set-union-heuristics-2e82","status":"publish","type":"post","link":"https:\/\/nabfollower.com\/blog\/disjoint-set-union-heuristics-2e82\/","title":{"rendered":"Disjoint Set Union \u0627\u06a9\u062a\u0634\u0627\u0641\u06cc – \u0627\u0646\u062c\u0645\u0646 DEV"},"content":{"rendered":"
\n

DSU \u06cc\u06a9\u06cc \u0627\u0632 \u0638\u0631\u06cc\u0641 \u062a\u0631\u06cc\u0646 \u062f\u0631 \u0633\u0627\u062e\u062a\u0627\u0631 \u062f\u0627\u062f\u0647 \u0647\u0627\u06cc \u067e\u06cc\u0627\u062f\u0647 \u0633\u0627\u0632\u06cc \u0627\u0633\u062a \u0648 \u0645\u0646 \u0628\u0627\u0631\u0647\u0627 \u062f\u0631 \u0632\u0646\u062f\u06af\u06cc \u0628\u0631\u0646\u0627\u0645\u0647 \u0646\u0648\u06cc\u0633\u06cc \u0631\u0642\u0627\u0628\u062a\u06cc \u062e\u0648\u062f \u0627\u0632 \u0622\u0646 \u0627\u0633\u062a\u0641\u0627\u062f\u0647 \u06a9\u0631\u062f\u0647 \u0627\u0645. \u0627\u06cc\u0646\u062a\u0631\u0646\u062a \u067e\u0631 \u0627\u0632 \u067e\u06cc\u0627\u062f\u0647 \u0633\u0627\u0632\u06cc \u0647\u0627\u06cc \u0645\u062e\u062a\u0644\u0641 \u0628\u0631\u0627\u06cc \u0622\u0646 \u0627\u0633\u062a\u060c \u0627\u0645\u0627 \u0645\u062a\u0623\u0633\u0641\u0627\u0646\u0647 \u062a\u0642\u0631\u06cc\u0628\u0627\u064b \u0647\u06cc\u0686 \u0645\u0642\u0627\u0644\u0647 \u0627\u06cc \u0648\u062c\u0648\u062f \u0646\u062f\u0627\u0631\u062f \u06a9\u0647 \u0627\u062b\u0628\u0627\u062a \u062e\u0648\u0628\u06cc \u0628\u0631\u0627\u06cc \u06a9\u0627\u0631\u0627\u06cc\u06cc DSU \u062f\u0627\u0634\u062a\u0647 \u0628\u0627\u0634\u062f\u060c \u062f\u0631 \u0627\u06cc\u0646 \u0645\u0642\u0627\u0644\u0647 \u0628\u0647 \u0628\u0647\u062a\u0631\u06cc\u0646 \u0646\u062d\u0648 \u0627\u06cc\u0646 \u0631\u0627\u0632 \u0631\u0627 \u06a9\u0634\u0641 \u062e\u0648\u0627\u0647\u0645 \u06a9\u0631\u062f. <\/p>\n

\u0633\u0627\u062e\u062a\u0627\u0631 \u062f\u0627\u062f\u0647 Trivial Disjoint Set Union \u0631\u0627 \u0645\u06cc \u062a\u0648\u0627\u0646 \u0628\u0647 \u0631\u0648\u0634 \u0632\u06cc\u0631 \u067e\u06cc\u0627\u062f\u0647 \u0633\u0627\u0632\u06cc \u06a9\u0631\u062f<\/p>\n

\n
class DSU \n{\n    private int[] parent;\n\n    void createSet(int vertex)\n    {\n        parent[vertex] = vertex;\n    } \n\n    bool isRepresentative(int vertex)\n    {\n        return parent[vertex] == vertex;\n    }\n\n    void findRepresentative(int vertex)\n    {\n        if (!isRepresentative(vertex))\n        {\n            return findRepresentative(parent[vertex]);\n        }\n\n        return vertex;\n    } \n\n\n    void mergeSets(int lhs, int rhs)\n    {\n        int rhsRepresentative = findRepresentative(rhs);\n        int lhsRepresentative = findRepresentative(lhs);\n\n        if (lhsRepresentative != rhsRepresentative)\n        {\n            parent[lhsRepresentative] = rhsRepresentative;\n        }\n    }\n}\n<\/code><\/pre>\n
\n
\n    \u0648\u0627\u0631\u062f \u062d\u0627\u0644\u062a \u062a\u0645\u0627\u0645 \u0635\u0641\u062d\u0647 \u0634\u0648\u06cc\u062f<\/title>\n    \n<\/svg><\/p>\n
    \u0627\u0632 \u062d\u0627\u0644\u062a \u062a\u0645\u0627\u0645 \u0635\u0641\u062d\u0647 \u062e\u0627\u0631\u062c \u0634\u0648\u06cc\u062f<\/title>\n    \n<\/svg><\/p>\n<\/div>\n<\/div>\n<\/div>\n
\u0628\u06cc\u0627\u06cc\u06cc\u062f \u0628\u0627 \u062f\u0648 DSU \u0627\u06a9\u062a\u0634\u0627\u0641\u06cc \u0628\u06cc \u0627\u0647\u0645\u06cc\u062a \u0634\u0631\u0648\u0639 \u06a9\u0646\u06cc\u0645<\/p>\n
\n
\n
\u0641\u0647\u0631\u0633\u062a \u0645\u0637\u0627\u0644\u0628<\/p>\nToggle<\/span><\/path><\/svg><\/svg><\/span><\/span><\/span><\/a><\/span><\/div>\n