Completing a Tree (Rosalind | English)

   

   

Hi everyone, how are you? This time, I want to discuss about one problem (bioinformatics problem) that exists in rosalind.info's web. The title is "Completing a Tree". For the reference, you can first check out the problem that will be discussed (here). 

The tree is always applying edge = node - 1 (image above, 5 = 6 - 1).

Overview 

In this problem, we will given an integer n and n integers a and b respectively. Integer a and b themself represent nodes that are interconnected, like tree concept in programming. 

Our task is determining the minimum amount of edge needed for connecting all of the nodes. 

The Code 

This is the code for solving this problem in java language: 

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. }
    

The Code Discription

We start from static static void solve() (line 12). The first thing that we will do is saving the dataset of the interconnected nodes in Map<Integer, Vector<Integer>> (line 15-21).

The next step is determining the total number of groups formed by the datasets above with the tracking method using breadth-first search algorithm (line 24-29).

The answer is the total number of groups formed minus one (line 31). 

Input dan Output

Like what you see, in the code above I used next() function (line 14, 17, 18) for entering the string-form dataset (which later I reformed it into integer-form dataset). In here, you can subtitute the next() function with the nextInt() function for entering the dataset by integer-form dataset directly.

And for the output I used out.println() function (line 31). That function is a modification from System.out.println() function which is very familiar in java. For more details, you can see the additional code for that modification (input and output) in my complete code at github. 

That's it. If you want to ask something, you can write it in the comment section below. I hope this article is useful and see you in the next article! 

Reference :

Source image 1 :https://www.facebook.com/ProjectRosalind/

Source image 2 :https://en.wikipedia.org/wiki/Tree_(graph_theory)