class Solution { int parents[] ; int size []; public int findparent(int u){ if(parents[u] == u) return u; int temp = findparent(parents[u]); parents[u] = temp; return temp; } public void merge(int p1 , int p2 ){ if(size[p1] > size[p2]){ parents[p2] = p1; size[p1] += size[p2]; } else{ parents[p1] = p2; size[p2] += size[p1]; } } public int minMalwareSpread(int[][] graph, int[] initial) { /* Q35 of graph playlist, DSU concept . 1) find components and merge them using DSU 2) here rank will be equal to size denoting size of the component 3) find parent of infected index and then their size and update answer accordingly */ int m = graph.length , n = graph[0].length; parents = new int[m]; size = new int[m]; for(int i = 0 ;i < m ; i++){ parents[i] = i; size[i] = 1; } //merging nodes and finding components and updating size of components for(int i = 0 ; i < m ; i ++){ for(int j = 0 ;j < n ; j++){ //if edge is present merge if(graph[i][j] ==1){ int p1 = findparent(i); int p2 = findparent(j); if(p1 != p2) merge(p1 , p2); } } } //making hashset to prevent duplicate answer HashSet<Integer> set = new HashSet<>(); int ans = Integer.MAX_VALUE, max_size = -1; //finding answer for virus for(int virus : initial){ int p1 = findparent(virus); if(size[p1] > max_size){ ans = virus ; max_size = size[p1]; } else if(size[p1] == max_size && virus < ans) ans = virus; } return ans; } }
Preview:
downloadDownload PNG
downloadDownload JPEG
downloadDownload SVG
Tip: You can change the style, width & colours of the snippet with the inspect tool before clicking Download!
Click to optimize width for Twitter