Completing a Tree (Rosalind)

  

   

Halo teman-teman, apa kabar? Kali ini saya ingin membahas sedikit tentang salah satu problem yang ada di web rosalind.info. Judulnya ialah "Completing a Tree". Sebagai acuan, teman-teman bisa cek dahulu problem yang akan kita bahas (disini). 

Grafik tree selalu mempunyai jumlah edge: node - 1 (contoh diatas, 5 = 6 - 1).

Overview 

Di problem ini kita akan disajikan bilangan integer n dan bilangan integer a dan b secara beruntun sebanyak n buah. Integer a dan b sendiri mewakili node-node yang saling bersambung, seperti konsep tree dalam dunia programming. 

Tugas kita ialah menentukan jumlah minimal dari edge atau "jembatan" yang diperlukan untuk membuat semua node tersambung. 

Kode Pengerjaan

Berikut kode pengerjaannya dalam bahasa java :

1. static void bfs1 (Map<Integer, Vector<Integer>> link, int[] arr, int grup, int i) {
2. Deque<Integer> antre = new ArrayDeque<>();
3. antre.addLast(i);
4. while (!antre.isEmpty()) {
5. int now = antre.pollFirst();
6. arr[now] = grup;
7. if (link.containsKey(now)) for (int x : link.get(now)) {
8. if (arr[x] == 0) antre.addLast(x);
9. }
10. }
11. }
12. static void solve() {
13. Scanner sc = new Scanner(System.in);
14. int n = Integer.parseInt(sc.next());
15. Map<Integer, Vector<Integer>> link = new HashMap<>();
16. while (sc.hasNext()) {
17. int a = Integer.parseInt(sc.next());
18. int b = Integer.parseInt(sc.next());
19. if (!link.containsKey(a)) link.put(a, new Vector<>());link.get(a).add(b);
20. if (!link.containsKey(b)) link.put(b, new Vector<>());link.get(b).add(a);
21. }
22. int[] arr = new int[n + 1];
23. int grup = 1;
24. for (int i = 1; i <= n; i++) {
25. if (arr[i] == 0) {
26. bfs1(link, arr, grup, i);
27. grup++;
28. }
29. }
30. grup--;
31. out.println(grup - 1);
32. }
    

Penjelasan Kode

Kita mulai dari static void solve() (baris 12). Pertama, yang akan kita lakukan ialah menyimpan data node-node yang saling menyambung di Map<Integer, Vector<Integer>> (baris 15-21). 

Langkah selanjutnya ialah kita tentukan dahulu jumlah total grup yang dibentuk oleh data-data diatas dengan metode tracking memakai algoritma breadth-first search. (baris 24-29). 

Jawabannya ialah jumlah total grup yang dibentuk dikurangi satu (baris 31). 

Input dan Output

Seperti yang teman-teman lihat; disini, saya memakai fungsi next() (baris 14, 17, 18) untuk meng-input data string (yang kemudian saya rubah ke integer). Disini, teman-teman bisa mengganti fungsi next() dengan fungsi nextInt() untuk langsung meng-input data integer-nya. 

Sedangkan untuk output-nya saya memakai fungsi out.println() (baris 31). Fungsi tersebut adalah modifikasi dari fungsi System.out.println() yang merupakan fungsi default di java. Untuk lebih jelasnya, teman-teman bisa melihat kode tambahan untuk memodifikasi fungsi tersebut (input maupun output) di versi lengkap kode saya di github. 

Sekian dari saya. Jika teman-teman ingin menanyakan sesuatu, teman-teman bisa menulisnya di kolom komentar. Semoga bermanfaat dan sampai jumpa di artikel berikutnya!

Referensi :

Sumber gambar 1 :https://www.facebook.com/ProjectRosalind/

Sumber gambar 2 :https://en.wikipedia.org/wiki/Tree_(graph_theory)