|
15-topshiriq.
L1 = [ 1 2 3 4 5 ]
L2 = [ 8 5 3 4 3 3 6 ]
L3 = [ 7 4 4 3 8 25 ]
1- L4 = L1+L2+L3 ni toping
2- L4 ro’yxatdan eng katta(kichik) elementni toping.
3- Eng ko’p qatnashgan elementlarni toping.
4- L4 ni to’plam sifatida shakllantiring.
5- To’plmani Kesishmasi bo’sh to’plam bo’lgan ikkita teng bo’lakka ajrating.
6- Ajratilgan bo’laklar ustida DSU algoritmini qo’llang.
7- Ajratilgan bo’laklardan quyidagi dastur kodi bo’yicha hisoblash ishlarini
amalga oshiring.
package com.interview.graph;
import java.util.HashMap;
import java.util.Map;
/* 1) makeSet
* 2) union
* 3) findSet
*
* k operatsiyalari uchun va umumiy n elementlar vaqt murakkabligi f(n)
bo'lgan joyda O(k*f(n))
* juda sekin o'sib borayotgan funksiya. Aksariyat hollarda f(n) <= 4 ta shunday
samarali
* umumiy vaqt O(k) bo'ladi.
*/
public class DisjointSet {
private Map map = new HashMap<>();
class Node {
long data;
Node parent;
int rank;
}
/**
* Create a set with only one element.
*/
public void makeSet(long data) {
Node node = new Node();
node.data = data;
node.parent = node;
node.rank = 0;
map.put(data, node);
}
/**
* Combines two sets together to one.
* Does union by rank
*
* @return true if data1 and data2 are in different set before union else false.
*/
public boolean union(long data1, long data2) {
Node node1 = map.get(data1);
Node node2 = map.get(data2);
Node parent1 = findSet(node1);
Node parent2 = findSet(node2);
//if they are part of same set do nothing
if (parent1.data == parent2.data) {
return false;
}
//else whoever's rank is higher becomes parent of other
if (parent1.rank >= parent2.rank) {
//increment rank only if both sets have same rank
parent1.rank = (parent1.rank == parent2.rank) ? parent1.rank + 1 :
parent1.rank;
parent2.parent = parent1;
} else {
parent1.parent = parent2;
}
return true;
}
/**
* Finds the representative of this set
*/
public long findSet(long data) {
return findSet(map.get(data)).data;
}
/**
* Find the representative recursively and does path
* compression as well.
*/
private Node findSet(Node node) {
Node parent = node.parent;
if (parent == node) {
return parent;
}
node.parent = findSet(node.parent);
return node.parent;
}
public static void main(String args[]) {
DisjointSet ds = new DisjointSet();
ds.makeSet(1);
ds.makeSet(2);
ds.makeSet(3);
ds.makeSet(4);
ds.makeSet(5);
ds.makeSet(6);
ds.makeSet(7);
ds.union(1, 2);
ds.union(2, 3);
ds.union(4, 5);
ds.union(6, 7);
ds.union(5, 6);
ds.union(3, 7);
System.out.println(ds.findSet(1));
System.out.println(ds.findSet(2));
System.out.println(ds.findSet(3));
System.out.println(ds.findSet(4));
System.out.println(ds.findSet(5));
System.out.println(ds.findSet(6));
System.out.println(ds.findSet(7));
}
}
18.71,42,13,71,97,71,42,16,68,57,59,48,18,46,1,78,7
86,82,88,33,62,23,56,21,51,32,2,53,24,37,22,89,46
43,95,64,9,28,47,5,60,83,76,92,97,36,90,34,91,76
import java.util.HashMap;
import java.util.Map;
public class DisjointSet {
private Map map = new HashMap<>();
class Node {
long data;
Node parent;
int rank;
}
public void makeSet(long data) {
System.out.println(data+"mn");
Node node = new Node();
node.data = data;
node.parent = node;
node.rank = 0;
map.put(data, node);
System.out.println(map);
}
* @return true if data1 and data2 are in different set before union else false.
*/
public boolean union(long data1, long data2) {
Node node1 = map.get(data1);
Node node2 = map.get(data2);
Node parent1 = findSet(node1);
Node parent2 = findSet(node2);
//if they are part of same set do nothing
if (parent1.data == parent2.data) {
return false;
}
//else whoever's rank is higher becomes parent of other
if (parent1.rank >= parent2.rank) {
//increment rank only if both sets have same rank
parent1.rank = (parent1.rank == parent2.rank) ? parent1.rank + 1 :
parent1.rank;
parent2.parent = parent1;
} else {
parent1.parent = parent2;
}
return true;
}
public long findSet(long data) {
return findSet(map.get(data)).data;
}
private Node findSet(Node node) {
Node parent = node.parent;
if (parent == node) {
return parent;
}
node.parent = findSet(node.parent);
return node.parent;
}
public static void main(String args[]) {
DisjointSet ds = new DisjointSet();
ds.makeSet(71);
ds.makeSet(42);
ds.makeSet(13);
ds.makeSet(71);
ds.makeSet(97);
ds.makeSet(71);
ds.makeSet(42);
ds.makeSet(16);
ds.makeSet(68);
ds.makeSet(57);
ds.makeSet(59);
ds.makeSet(48);
ds.makeSet(18);
ds.makeSet(46);
ds.makeSet(1);
ds.makeSet(78);
ds.makeSet(7);
}
}
Do'stlaringiz bilan baham: |
