(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;
}
}
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
Post a Comment