(UVA) Spreading the News - Solution

I have used the Breadth-First Search approach to solve this problem.
 
import java.io.*;
import java.util.*;

class Main  {
    public static HashMap<Integer, ArrayList<Integer>> adjList = new HashMap<Integer, ArrayList<Integer>>();
   
    public static void printAnswer(int maxDailyBoomSize, int firstDayBoom) {
        if (maxDailyBoomSize == 0) {
            System.out.println("0");
        }
        else {
            System.out.println(maxDailyBoomSize + " " + firstDayBoom);
        }
    }
   
    public static int[] bfs(int start, int numFriends) {
        Queue<Dissemination> queue = new ArrayDeque<Dissemination>();
        Dissemination d = new Dissemination(start, 0);
        queue.add(d);
       
        HashSet<Integer> addedToQueue = new HashSet<Integer>();
        addedToQueue.add(start);
       
        int[] days = new int[numFriends];
       
        while (queue.size() > 0) {
            Dissemination tmp = queue.poll();
            int currPerson = tmp.person;
            int day = tmp.day;
           
            ArrayList<Integer> friends = adjList.get(currPerson);
            for (int i = 0; i < friends.size(); i++) {
                int currFriend = friends.get(i);
                if (!addedToQueue.contains(currFriend)) {
                    d = new Dissemination(currFriend, day+1);
                    queue.add(d);
                    addedToQueue.add(currFriend);
                   
                    days[day+1]++;
                }
            }
        }
       
        return days;
    }
   
    public static void readCases(BufferedReader br, int numCases, int numEmployees) throws NumberFormatException, IOException {
        for (int i = 0; i < numCases; i++) {
            int source = reader(br);
            int[] days = bfs(source, numEmployees);
            int maxDailyBoomSize = -1;
            int firstDayBoom = -1;
            for (int j = 0; j < numEmployees; j++) {
                if (days[j] > maxDailyBoomSize) {
                    maxDailyBoomSize = days[j];
                    firstDayBoom = j;
                }
            }
           
            printAnswer(maxDailyBoomSize, firstDayBoom);
        }
    }
   
    public static void readFriendships(BufferedReader br, int numEmployees) throws NumberFormatException, IOException {
        for (int i = 0; i < numEmployees; i++) {
            int numFriends = reader(br);
            for (int j = 0; j < numFriends; j++) {
                int friend = reader(br);
                adjList.get(i).add(friend);
            }
        }
    }
   
    public static void initAdjList(int numEmployees) {
        for (int i = 0; i < numEmployees; i++) {
            adjList.put(i, new ArrayList<Integer>());
        }
    }
   
    public static int reader(BufferedReader br) throws NumberFormatException, IOException {     
        int n;
        int resp = 0;      
      
        while (true) {         
            n = br.read();         
            if (n >= '0' && n <= '9') {
                break;
            } 
        }
           
        while (true) {         
            resp = resp*10 + n-'0';         
            n = br.read();         
            if (n < '0' || n > '9') {
                break;     
            }
        }
      
        return resp;     
    }
   
    public static void process() throws NumberFormatException, IOException {   
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       
        int numEmployees = reader(br);
        initAdjList(numEmployees);
       
        readFriendships(br, numEmployees);
       
        int numCases = reader(br);
        readCases(br, numCases, numEmployees);
               
        return;
    }
   
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();

        System.exit(0);
    }
}

class Dissemination {
    int person;
    int day;
   
    public Dissemination(int person, int day) {
        this.person = person;
        this.day = day;
    }
}

Comments

Popular posts from this blog

(Coderbyte) Dash Insert II - Solução

(Coderbyte) Run Length - Solução

(Coderbyte) Counting Minutes I - Solução