JAVA_Practice/DSU.java at main · jayamukh/JAVA_Practice · GitHub

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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
/* *****************************************************************************
 *  Name:              Ada Lovelace
 *  Coursera User ID:  123456
 *  Last modified:     October 16, 1842
 **************************************************************************** */

import java.util.ArrayList;
import java.util.Arrays;

class DSU {
    int[] par;
    int[] size;

    public int findPar(int u) {
        if (par[u] == u) return u;

        int p = findPar(par[u]);

        par[u] = p;

        return p;
    }

    public void merge(int p1, int p2) {
        if (size[p1] >= size[p2]) {
            par[p2] = p1;
            size[p1] += size[p2];
        }
        else {
            par[p1] = p2;
            size[p2] += size[p1];
        }
    }


    public ArrayList<Integer>[] createSpanningTree(int V, int[][] edges) {
        ArrayList<Integer>[] graph = new ArrayList[V];

        for (int i = 0; i < V; i++) {
            graph[i] = new ArrayList<>();
        }

        par = new int[V];
        size = new int[V];

        for (int i = 0; i < V; i++) {
            par[i] = i;
            size[i] = 1;
        }

        for (int[] edge : edges) {
            int u = edge[0];
            int v = edge[1];

            int p1 = findPar(u);
            int p2 = findPar(v);

            if (p1 != p2) {
                merge(p1, p2);
                addEdge(graph, u, v);
            }
        }

        return graph;

    }

    public void addEdge(ArrayList<Integer>[] graph, int u, int v) {
        graph[u].add(v);
        graph[v].add(u);
    }

    public static void main(String[] args) {

    }

    ///////////////////Kruskal///////////////////////

    public static class Edge {
        int v;
        int w;

        Edge(int v, int w) {
            this.v = v;
            this.w = w;
        }
    }

    public void addEdge_kruskal(ArrayList<Edge>[] graph, int u, int v, int w) {
        graph[u].add(new Edge(v, w));
        graph[v].add(new Edge(u, w));
    }

    public ArrayList<Edge>[] kruskal(int[][] edges, int V) {
        ArrayList<Edge>[] mst = new ArrayList[V];

        for (int i = 0; i < V; i++) {
            mst[i] = new ArrayList<>();
        }

        Arrays.sort(edges, (int[] a, int[] b) -> {
            return a[2] - b[2];

        });
        par = new int[V];
        size = new int[V];

        int total_weight = 0;

        for (int[] edge : edges) {
            int u = edge[0];
            int v = edge[1];
            int w = edge[2];

            int p1 = findPar(u);
            int p2 = findPar(v);

            if (p1 != p2) {
                merge(p1, p2);
                total_weight += w;
                addEdge_kruskal(mst, u, v, w);
            }
        }

        System.out.println(total_weight);
        return mst;
    }

}