DSU.code-snippets

{
	"Disjoint_Set_Union": {
		"prefix": "DSU",
		"body": [
		  "struct DSU {",
		  "    ",
		  "    vector < int > parent, Gsize;",
		  "",
		  "    DSU(int MaxNodes){",
		  "        parent.resize(MaxNodes + 5);",
		  "        Gsize.resize(MaxNodes + 5);",
		  "        for(int i = 1; i <= MaxNodes; i++)",
		  "          parent[i] = i, Gsize[i] = 1;",
		  "    }",
		  "    ",
		  "    int find_leader(int node){",
		  "        return parent[node] = (parent[node] == node ? node : find_leader(parent[node]));",
		  "    }",
		  "",
		  "    bool is_same_sets(int u, int v){",
		  "        return find_leader(u) == find_leader(v);",
		  "    }",
		  "",
		  "    void union_sets(int u, int v){",
		  "        int leader_u = find_leader(u), leader_v = find_leader(v);",
		  "        if(leader_u == leader_v) return;",
		  "        if(Gsize[leader_u] < Gsize[leader_v]) swap(leader_u, leader_v);",
		  "        Gsize[leader_u] += Gsize[leader_v], parent[leader_v] = leader_u;",
		  "    }",
		  "",
		  "    int get_size(int node){",
		  "        return Gsize[find_leader(node)];",
		  "    }",
		  "};"
		],
		"description": "Disjoint_Set_Union"
	}
}