SPOJ – HMRO

Given transitive dependency of some string and duplication of the keys, use the keys that pertains to last value and the final value of the dependency to replace the original values.

1
4
4564564564 ABC3
4564564564 ABC4
1231231231 ABC2
1231231231 ABC1
2
ABC2 ABC3
ABC3 ABC4
6
1231231231
1231231231
4564564564
1231231231
1231231231
4564564564

Output:
1231231231 ABC1
1231231231 ABC1
4564564564 ABC4
1231231231 ABC1
1231231231 ABC1
4564564564 ABC4

For 1 test case and 4 values with different codes, and the transitive dependecy, format the 6 answers with proper code.

As we can see from the example ABC2 should be replaced with ABC3, and ABC3 should be replaced with ABC4. Therefore, anywhere ABC2 is mentioned, it should be replaced with ABC4. Also maitaining the last value to choose, the code for 1231231231 should be ABC1. As that’s the last value in input and does not have any replacement.

Here is the code.

Note: Since there can be several inputs each ranging upto 10000, it is advisable to limit the no. of inner loops. For that reason, I have used HashMap, where it makes sense.

import java.util.*;
import java.lang.*;

class HMRO {

public static void main(String[] args) {
 Scanner sc = new Scanner(System.in);
 int s = sc.nextInt();
 for (int t = 0; t < s; t++) {
 int p = sc.nextInt();
 String[][] parr = new String[p][2];
 for (int i = 0; i < p; i++) {
 parr[i][0] = sc.next();
 parr[i][1] = sc.next();
 }

int z = sc.nextInt();
 String[][] zarr = new String[z][2];
 for (int i = 0; i < z; i++) {
 zarr[i][0] = sc.next();
 zarr[i][1] = sc.next();
 }
 HashMap < String, String > zarrmap = reformatMRO(zarr);

int peas = sc.nextInt();
 String[] peasarr = new String[peas];
 for (int i = 0; i < peas; i++) {
 peasarr[i] = sc.next();
 }

HashMap < String, String > parrmap = reformat(parr, zarrmap);

for (int i = 0; i < peas; i++) {
 System.out.println(peasarr[i] + " " + parrmap.get(peasarr[i]));
 }
 }

}

static HashMap < String, String > reformatMRO(String[][] zarr) {
 HashMap < String, String > map = new HashMap < > ();
 for (int i = zarr.length - 1; i >= 0; i--) {
 String value = map.get(zarr[i][1]);
 map.put(zarr[i][0], value == null ? zarr[i][1] : value);
 }

return map;
 }

static HashMap < String, String > convertToMap(String[][] parr) {
 HashMap < String, String > map = new HashMap < String, String > ();
 for (int i = 0; i < parr.length; i++) {
 map.put(parr[i][0], parr[i][1]);
 }
 return map;
 }

static HashMap < String, String > reformat(String[][] parr, HashMap < String, String > zarrmap) {
 int M = parr.length;
 HashMap < String, String > map = new HashMap < > ();

for (int i = 0; i < M; i++) {
 String value = zarrmap.get(parr[i][1]);
 if (value != null) {
 map.put(parr[i][0], value);
 } else {
 map.put(parr[i][0], parr[i][1]);
 }
 }

return map;
 }
}