OJ Board

Code: Select all

AC

Code: Select all

      if(strcmp(c,"no.child")==0 && strcmp(p,"no.parent")==0) break; 

Code: Select all

   for(i=0;i<jum;i++) 
      if(fam[i].parent) fam[i].n=fam[i].parent->n+1; 

Code: Select all

import java.io.IOException;
import java.util.HashMap;
import java.util.StringTokenizer;

public class P115 {
	int[] parent;
	public static void main(String[] args) {
		int index = 1;
		HashMap hm = new HashMap();
		String line = ReadLn(100);
		StringTokenizer st = new StringTokenizer(line);
		P115 p = new P115();
		p.parent = new int[300];
		String[] words = new String[2];
		words[0] = st.nextToken();
		words[1] = st.nextToken();
		while (!words[0].equals("no.child")) {
			if (hm.get(words[0]) == null)
				hm.put(words[0], (Object) (Integer.valueOf(index++)));
			if (hm.get(words[1]) == null)
				hm.put(words[1], Integer.valueOf(index++));
			p.parent[((Integer) hm.get(words[0])).intValue()] = ((Integer) hm
					.get(words[1])).intValue();
			line = ReadLn(80);
			st = new StringTokenizer(line);
			words[0] = st.nextToken();
			words[1] = st.nextToken();
		}
		while ((line = ReadLn(100)) != null) {
			st=new StringTokenizer(line);
			words[0]=st.nextToken();
			words[1]=st.nextToken();
			int ind1 = -1;
			if (hm.get(words[0]) != null)
				ind1 = ((Integer) hm.get(words[0])).intValue();
			int ind2 = -1;
			if (hm.get(words[1]) != null)
				ind2 = ((Integer) hm.get(words[1])).intValue();

			if (ind1 != -1 && ind2 != -1) {
				int[] way1 = new int[index + 1000];
				int[] way2 = new int[index + 1000];
				p.dfsInstead(ind1, way1);
				p.dfsInstead(ind2, way2);
				int w1 = p.findlastIndex(way1);
				int w2 = p.findlastIndex(way2);
				/*
				 * int w1k=w1; int w2k=w2;
				 */
				int commonIndex = 0;
				if (way1[w1 - 1] != way2[w2 - 1]) {
					System.out.println("no relation");
				} else {
					while (w1 > 0 && w2 > 0 && way1[--w1] == way2[--w2]) {
						commonIndex++;
					}
					if (way1[w1 + 1] == way2[w2 + 1] && w1 == w2 && w1 == 0)
						System.out.println("sibling");
					else if (w2 == 1 && w1 == 0 && way2[w2] == way1[w1])
						System.out.println("parent");
					else if (w1 == 1 && w2 == 0 && way2[w2] == way1[w1])
						System.out.println("child");
					else if (w2 == 0 && way1[w1] == way2[w2]) {
						for (int i = 0; i < w1 - 2; i++) {
							System.out.print("great ");
						}
						System.out.println("grand child");
					} else if (w1 == 0 && way1[w1] == way2[w2]) {
						for (int i = 0; i < w2 - 2; i++) {
							System.out.print("great ");
						}
						System.out.println("grand parent");
					} else {
						System.out.print(Math.min(w1, w2) + " cousin");
						if (w1!=w2) {
							System.out.print(" removed " + (Math.abs(w1 - w2)));
						}
						System.out.println();
					}
				}
			} else {
				System.out.println("no relation");
			}
		}
	}

	int findlastIndex(int[] way) {
		int ind = 0;
		while (way[ind++] != 0)
			;
		return ind - 1;
	}

	void dfsInstead(int index, int[] array) {
		int d = 0;
		while (index != 0) {
			array[d++] = index;
			index = parent[index];
		}
	}

	static String ReadLn(int maxLg) // utility function to read from stdin
	{
		byte lin[] = new byte[maxLg];
		int lg = 0, car = -1;

		try {
			while (lg < maxLg) {
				car = System.in.read();
				if ((car < 0) || (car == '\n'))
					break;
				lin[lg++] += car;
			}
		} catch (IOException e) {
			return (null);
		}

		if ((car < 0) && (lg == 0))
			return (null); // eof
		return (new String(lin, 0, lg));
	}

}

Code: Select all

A B
A C
no.child no.parent

Code: Select all

A B
no.child no.parent
A A

Code: Select all

A B
A B
no.child no.parent
A B

Code: Select all

A B
no.child no.parent
no.child B

Code: Select all

no relation