Google Code Jam Notes - Bad Horse - Java

Problem

Retrieved from: http://code.google.com/codejam/contest/2845486/dashboard#s=p2

As the leader of the Evil League of Evil, Bad Horse has a lot of problems to deal with. Most recently, there have been far too many arguments and far too much backstabbing in the League, so much so that Bad Horse has decided to split the league into two departments in order to separate troublesome members. Being the Thoroughbred of Sin, Bad Horse isn't about to spend his valuable time figuring out how to split the League members by himself. That what he's got you -- his loyal henchman -- for.

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test case starts with a positive integer M on a line by itself -- the number of troublesome pairs of League members. The next M lines each contain a pair of names, separated by a single space.

Output

For each test case, output one line containing "Case #x: y", where x is the case number (starting from 1) and y is either "Yes" or "No", depending on whether the League members mentioned in the input can be split into two groups with neither of the groups containing a troublesome pair.

Limits

1 ≤ T ≤ 100.
Each member name will consist of only letters and the underscore character.
Names are case-sensitive.
No pair will appear more than once in the same test case.
Each pair will contain two distinct League members.

Small dataset

1 ≤ M ≤ 10.

Large dataset

1 ≤ M ≤ 100.

Sample

Input	Output
2 1 Dead_Bowie Fake_Thomas_Jefferson 3 Dead_Bowie Fake_Thomas_Jefferson Fake_Thomas_Jefferson Fury_Leika Fury_Leika Dead_Bowie	Case #1: Yes Case #2: No

Analysis:

Solve this problem by using DFS, since large data set is 100, we can implement it recursively.

Time complexity: O(n^2)

My solution: (Your opinion is highly appreciated)

[java] view plaincopy






package codeJam.google.com;  
  
import java.io.BufferedReader;  
import java.io.FileReader;  
import java.io.FileWriter;  
import java.io.IOException;  
import java.util.HashSet;  
  
/** 
 * @author Zhenyi 2013 Dec 21, 2013 11:37:20 AM 
 */  
public class BadHorse {  
    static String[] st;  
    static int M;  
  
    public static void main(String[] args) throws IOException {  
        BufferedReader in = new BufferedReader(new FileReader(  
                "C:/Users/Zhenyi/Downloads/A-small-practice-1.in"));  
        FileWriter out = new FileWriter(  
                "C:/Users/Zhenyi/Downloads/A-small-practice-1.out");  
        // BufferedReader in = new BufferedReader(new  
        // FileReader("C:/Users/Zhenyi/Downloads/A-small-practice-2.in"));  
        // FileWriter out = new  
        // FileWriter("C:/Users/Zhenyi/Downloads/A-small-practice-2.out");  
  
        int T = new Integer(in.readLine());  
  
        for (int cases = 1; cases <= T; cases++) {  
            M = new Integer(in.readLine());  
            boolean result = false;  
            st = new String[M];  
            for (int i = 0; i < M; i++) {  
                st[i] = in.readLine();  
            }  
  
            HashSet<String> st1 = new HashSet<String>();  
            HashSet<String> st2 = new HashSet<String>();  
            result = travesal(M, st1, st2);  
  
            if (result) {  
                out.write("Case #" + cases + ": " + "Yes" + "\n");  
            } else {  
                out.write("Case #" + cases + ": " + "No" + "\n");  
            }  
        }  
        in.close();  
        out.flush();  
        out.close();  
    }  
  
    private static boolean travesal(int m, HashSet<String> st1,  
            HashSet<String> st2) {  
        // TODO Auto-generated method stub  
        if (m == 0) {  
            return true;  
        }  
        int n = M - m;  
        String[] s = st[n].split("\\s");  
        if (!st1.contains(s[1]) && !st2.contains(s[0])) {  
            int tmp1 = 0;  
            int tmp2 = 0;  
            if (st1.contains(s[0]))  
                tmp1 = 1;  
            if (st2.contains(s[1]))  
                tmp2 = 1;  
            st1.add(s[0]);  
            st2.add(s[1]);  
            if (travesal(m - 1, st1, st2)) {  
                return true;  
            }  
            if (tmp1 == 0) {  
                st1.remove(s[0]);  
            }  
            if (tmp2 == 0) {  
                st2.remove(s[1]);  
            }  
        }  
  
        if (!st1.contains(s[0]) && !st2.contains(s[1])) {  
            int tmp1 = 0;  
            int tmp2 = 0;  
            if (st1.contains(s[1]))  
                tmp1 = 1;  
            if (st2.contains(s[0]))  
                tmp2 = 1;  
            st1.add(s[1]);  
            st2.add(s[0]);  
            if (travesal(m - 1, st1, st2)) {  
                return true;  
            }  
            if (tmp1 == 0) {  
                st1.remove(s[1]);  
            }  
            if (tmp2 == 0) {  
                st2.remove(s[0]);  
            }  
        }  
        return false;  
  
    }  
}