package problemsPackage;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class IsenbayevNumbers {
    public static void main(String args[]) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

        int numberOfTeams = Integer.parseInt(in.readLine());

        // Node containing Names of progers in team
        LinkedList<String[]> teamsList = new LinkedList<String[]>();

        LinkedList<String> uniqueParticipantsName = new LinkedList<String>();

        while (numberOfTeams != 0) {
            StringTokenizer tokenizer = new StringTokenizer(in.readLine(), " ");
            String members[] = new String[3];
            int i = 0;
            while (tokenizer.hasMoreTokens()) {
                members[i] = tokenizer.nextToken();
                addToList(uniqueParticipantsName, members[i]);
                i++;
            }
            teamsList.add(members);
            numberOfTeams--;
        }
        int array[][] = new int[uniqueParticipantsName.size()][uniqueParticipantsName.size()];
        fillArray(array,uniqueParticipantsName,teamsList);
        int participants = uniqueParticipantsName.size();
        int esenId = getIndex("Isenbaev", uniqueParticipantsName);

        int[] tentativeDistances = new int[participants];
        LinkedList<Integer>unvisitedNodes = new LinkedList<Integer>();

        for(int i=0;i<participants;i++){
            unvisitedNodes.add(i);
            if(i==esenId) tentativeDistances[i]=0;
            else tentativeDistances[i]=4000;
        }

        while(unvisitedNodes.size()!=0){
            int node  = getCurrentNode(tentativeDistances,unvisitedNodes);
            processNode(node,tentativeDistances,unvisitedNodes,array);
        }
        String names[] = new String[uniqueParticipantsName.size()];
        for(int i=0;i<uniqueParticipantsName.size();i++){
            names[i]=uniqueParticipantsName.get(i);
        }

        java.util.Arrays.sort(names);

        for(int i=0;i<names.length;i++){
            int index = getIndex(names[i], uniqueParticipantsName);
            int distance = tentativeDistances[index];
            if(distance!=4000)
                System.out.print(names[i]+" "+distance+"\n");
            else System.out.print(names[i]+" undefined\n");
        }
    }







    private static void processNode(int node, int[] tentativeDistances,
            LinkedList<Integer> unvisitedNodes, int[][] array) {

            LinkedList<Integer>neighbors = new LinkedList<Integer>();
            for(int j=0;j<array.length;j++){
                if(node!=j)
                    if(array[node][j]==1) neighbors.add(j);
            }

            for(int i=0;i<neighbors.size();i++){
                if(tentativeDistances[neighbors.get(i)]>tentativeDistances[node]+1)
                    tentativeDistances[neighbors.get(i)]=tentativeDistances[node]+1;
            }

            for(int i=0;i<unvisitedNodes.size();i++){
                if(unvisitedNodes.get(i)==node){
                    unvisitedNodes.remove(i);
                    break;
                }
            }
    }







    private static int getCurrentNode(int[] tentativeDistances,
            LinkedList<Integer> unvisitedNodes) {
        int minimum=10000;
        int index=0;
        for(int i=0;i<unvisitedNodes.size();i++){
            if(tentativeDistances[unvisitedNodes.get(i)]<minimum){
                minimum=tentativeDistances[unvisitedNodes.get(i)];
                index=unvisitedNodes.get(i);
            }
        }
        return index;
    }



    /**
     * Fill twodimensional array
     * @param array
     * @param uniqueParticipantsName
     * @param teamsList
     */
    private static void fillArray(int[][] array,
            LinkedList<String> uniqueParticipantsName,
            LinkedList<String[]> teamsList) {
        for(int i=0;i<uniqueParticipantsName.size();i++){
            String name = uniqueParticipantsName.get(i);
            for(int j=0;j<teamsList.size();j++){
                boolean exist=false;
                if(teamsList.get(j)[0].equalsIgnoreCase(name) || teamsList.get(j)[1].equalsIgnoreCase(name) || teamsList.get(j)[2].equalsIgnoreCase(name)) exist=true;
                if(exist){
                    if(!teamsList.get(j)[0].equalsIgnoreCase(name)) array[getIndex(name, uniqueParticipantsName)][getIndex(teamsList.get(j)[0], uniqueParticipantsName)]=1;
                    if(!teamsList.get(j)[1].equalsIgnoreCase(name)) array[getIndex(name, uniqueParticipantsName)][getIndex(teamsList.get(j)[1], uniqueParticipantsName)]=1;
                    if(!teamsList.get(j)[2].equalsIgnoreCase(name))    array[getIndex(name, uniqueParticipantsName)][getIndex(teamsList.get(j)[2], uniqueParticipantsName)]=1;
                }
            }
        }
    }


    /**
     * Index of name in list.
     * @param name
     * @param uniqueParticipantsName
     * @return
     */
    private static int getIndex(String name,LinkedList<String> uniqueParticipantsName){
        int index=0;
        for(int i=0;i<uniqueParticipantsName.size();i++){
            if(uniqueParticipantsName.get(i).equalsIgnoreCase(name)){
                index=i;
                break;
            }
        }
        return index;
    }


    /**
     * Store unique participant names into list
     * @param uniqueParticipantsName
     * @param string
     */
    private static void addToList(LinkedList<String> uniqueParticipantsName,
            String string) {
        boolean exist = false;
        for (int i = 0; i < uniqueParticipantsName.size(); i++) {
            if (uniqueParticipantsName.get(i).equalsIgnoreCase(string)) {
                exist = true;
                break;
            }
        }
        if (!exist)
            uniqueParticipantsName.add(string);
    }

}

Edited by author 22.02.2012 14:51

Try this test:

1
a b c

Answer is

a undefined
b undefined
c undefined

1
Isen Is Isenbaeva