This is a programming challenge in Czeck. My translation follows.
Does anyone know what the time complexity of my code is?
Input: The first line contains 2 integers: the number of animals 1 ≤N ≤100 and the number of their potential sponsors 1 ≤M ≤200. The following are N lines with information about each animal: the unique integer ID of the nth animal 0 ≤In <N and its one-word name. Animal names are also unique. Behind them are M lines with information about potential sponsors. Each line begins with the first name of the m-th sponsor and the number of animals 1 ≤Pm≤N, one of which is one willing to sponsor. The Pm ID of these animals follows. The first name of each sponsor is always unique.
Output: On the first line, write Yes, if all the animals find a sponsor, No otherwise. For all the animals for which you have found a sponsor, write the name of the animal on a separate line and the name of his sponsor separated by a space. Sort the rows in ascending alphabetical order by name animal. The task can have more than one correct solution, write any of them.
Example:
input:
7 8
1 cow
0 elephant
3 pig
2 gorilla
5 rhinoceros
6 tapir
4 kangaroo
Celestin 3 0 1 3
Hubert 2 4 5
Emma 2 4 6
Felix 1 6
Bert 4 0 1 2 6
Anna 5 0 2 3 4 5
Denis 1 6
Gustav 1 6
Output:
No
gorilla Bert
kangaroo Emma
elephant Celestina
pig Anna
rhinoceros Hubert
tapir Felix
Code:
import java.util.*;
class Animals
{
//S is number of sponsors, A is number of animals
static int S = 0;
static int A = 0;
//DFS
boolean bpm(boolean bpGraph[][], int u, boolean seen[], int matchR[]){
for (int v = 0; v < A; v++){
//does the sponsor want to sponsor this animal?
if (bpGraph[u][v] && !seen[v])
{
seen[v] = true;
if (matchR[v] < 0 || bpm(bpGraph, matchR[v], seen, matchR)){
matchR[v] = u;
return true;
}
}
}
return false;
}
// returns an array of which sponsor sponsors what animal
int[] maxBPM(boolean bpGraph[][])
{
int matchR[] = new int[A];
for(int i = 0; i < A; ++i)
matchR[i] = -1;
for (int a = 0; a < S; a++){
//indicate that no animal have been seen yet
boolean seen[] =new boolean[A];
for(int i = 0; i < A; ++i)
seen[i] = false;
//find if animal "a" can get sponsor
bpm(bpGraph, a, seen, matchR);
}
return matchR;
}
public static void main (String[] args){
//input
Scanner scn = new Scanner(System.in);
List<Animal> animalsID = new ArrayList<>();
System.out.println("Input: ");
A = scn.nextInt();
S = scn.nextInt();
scn.nextLine();
boolean bpGraph[][] = new boolean[S][A];
//load animals
for (int i = 0; i < A; i++) {
int id = scn.nextInt();
String name = scn.next();
scn.nextLine();
animalsID.add(new Animal(id, name));
}
//load sponsors
String namesSponsors[] = new String[S];
for (int i = 0; i < S; i++) {
namesSponsors[i] = scn.next();
int numberCanSponsor = scn.nextInt();
for (int j = 0; j < numberCanSponsor; j++) {
bpGraph[i][scn.nextInt()] = true;
}
scn.nextLine();
}
//BPM
Animals a = new Animals();
int[] result = a.maxBPM(bpGraph);
//output
System.out.println("\Output:");
boolean allAnimalsAreSponsored = true;
for (int i : result) {
if (i == -1){
allAnimalsAreSponsored = false;
}
}
if (allAnimalsAreSponsored){
System.out.println("Yes");
}else{
System.out.println("No");
}
for (int i = 0; i < A; i++) {
if (result[i] != -1){
for (Animal animal : animalsID) {
if (animal.getId() == i) {
System.out.print(animal.getName() + " ");
}
}
System.out.println(namesSponsors[result[i]]);
}
}
}
}
public class Animal {
private int id;
private String name;
Animal(int id, String name){
this.id = id;
this.name = name;
}
int getId(){
return id;
}
String getName(){
return name;
}
}
I'm a beginner, so the code looks awful. But I tried to make some comments.
Do you have any suggestions on how to simplify the script?