Company Компанија AIPS kolokviumska, juni 2019

/*АПС - КОМПАНИЈА
Во една компанија организацијата на работните позиции е дадена како пар (вработен,менаџер) кој кажува кој вработен под кој пенаџер припаѓа. Потребно е да се направи некоја статистика во компанијата и според тоа треба да се даде извештај за тоа колку вработени менаџери од компанијата, колку вработени имаат под нив. Може да се случи менаџер на некои вработени да биде надворешно лице. Еден вработен може да припаѓа на само еден менаџер.

ВЛЕЗ: Во првиот ред од влезот е даден бројот на парови кои ќе се внесува N (N<=10000), а во секој нареден ред се дадени паровите (име_вработен, име_менаџер).

ИЗЛЕЗ: Листата со имињата на вработените менаџери во компанијата и тоа колку вработени имаат под нивно раководство.

ДЕЛУМНО РЕШЕНИЕ: Задачата се смета за делумно решена доколку се поминати 7 тест примери.

ЗАБЕЛЕШКА: Задачата треба да се реши со помош на хеширање.

 Мој коментар:
Не знам дали смее да се користат готови класи од јава, како import java.util.LinkedList.
Ако не смее, сличен ефект може да се постигне со низа или SLL/DLL.
НАПОМЕНА: МЕНАЏЕР МОЖЕ ДА БИДЕ НАДВОРЕШНО ЛИЦЕ, па за да сме сигурни дали да го печатиме, мора прво да се провери дали е вработен на некој друг менаџер или е вработен на самиот себе.
Ако е вработен на сам себе, НЕ СЕ БРОИ во вработени.
/*

/* dva test primeri
6
Aleks Marko
Beti Marko
Marko Filip
Darko Elena
Elena Filip
Filip Filip

treba da se dobie:
Marko = 2, Filip = 2, Elena = 1
 */
/*
5
Aleks Marko
Beti Marko
Marko Filip
Darko Elena
Elena Filip
treba da se dobie:
Marko = 2, Elena = 1
 */

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

class MapEntry<K extends Comparable<K>,E> implements Comparable<K> {

    // Each MapEntry object is a pair consisting of a key (a Comparable
    // object) and a value (an arbitrary object).
    K key;
    E value;

    public MapEntry (K key, E val) {
        this.key = key;
        this.value = val;
    }

    public int compareTo (K that) {
        // Compare this map entry to that map entry.
        @SuppressWarnings("unchecked")
        MapEntry<K,E> other = (MapEntry<K,E>) that;
        return this.key.compareTo(other.key);
    }

    public String toString () {
        return "<" + key + "," + value + ">";
    }
}


class SLLNode<E> {
    protected E element;
    protected SLLNode<E> succ;

    public SLLNode(E elem, SLLNode<E> succ) {
        this.element = elem;
        this.succ = succ;
    }

    @Override
    public String toString() {
        return element.toString();
    }
}

class CBHT<K extends Comparable<K>, E> {

    // An object of class CBHT is a closed-bucket hash table, containing
    // entries of class MapEntry.
    private SLLNode<MapEntry<K,E>>[] buckets;

    @SuppressWarnings("unchecked")
    public CBHT(int m) {
        // Construct an empty CBHT with m buckets.
        buckets = (SLLNode<MapEntry<K,E>>[]) new SLLNode[m];
    }

    private int hash(K key) {
        // Translate key to an index of the array buckets.
        return Math.abs(key.hashCode()) % buckets.length;
    }

    public SLLNode<MapEntry<K,E>> search(K targetKey) {
        // Find which if any node of this CBHT contains an entry whose key is
        // equal
        // to targetKey. Return a link to that node (or null if there is none).
        int b = hash(targetKey);
        for (SLLNode<MapEntry<K,E>> curr = buckets[b]; curr != null; curr = curr.succ) {
            if (targetKey.equals(((MapEntry<K, E>) curr.element).key))
                return curr;
        }
        return null;
    }

    public void insert(K key, E val) {      // Insert the entry <key, val> into this CBHT.
        MapEntry<K, E> newEntry = new MapEntry<K, E>(key, val);
        int b = hash(key);
        for (SLLNode<MapEntry<K,E>> curr = buckets[b]; curr != null; curr = curr.succ) {
            if (key.equals(((MapEntry<K, E>) curr.element).key)) {
                // Make newEntry replace the existing entry ...
                curr.element = newEntry;
                return;
            }
        }
        // Insert newEntry at the front of the 1WLL in bucket b ...
        buckets[b] = new SLLNode<MapEntry<K,E>>(newEntry, buckets[b]);
    }

    public void delete(K key) {
        // Delete the entry (if any) whose key is equal to key from this CBHT.
        int b = hash(key);
        for (SLLNode<MapEntry<K,E>> pred = null, curr = buckets[b]; curr != null; pred = curr, curr = curr.succ) {
            if (key.equals(((MapEntry<K,E>) curr.element).key)) {
                if (pred == null)
                    buckets[b] = curr.succ;
                else
                    pred.succ = curr.succ;
                return;
            }
        }
    }

    public String toString() {
        String temp = "";
        for (int i = 0; i < buckets.length; i++) {
            temp += i + ":";
            for (SLLNode<MapEntry<K,E>> curr = buckets[i]; curr != null; curr = curr.succ) {
                temp += curr.element.toString() + " ";
            }
            temp += "\n";
        }
        return temp;
    }

}


public class Kompanija {

    public static void main( String[]args ) throws IOException{

        BufferedReader br = new BufferedReader( new InputStreamReader( System.in ));
        int N = Integer.parseInt( br.readLine() );

        CBHT<String, LinkedList<String> > hash = new CBHT<>( 2 * N ); // vo linked list ke gi cuvam site vraboteni za koi e odgovoren eden menadzer
        String []menadzeri = new String[ 100 ]; // gi stavam menadzerite za podocna da mozam da pristapam do niv
        int menadzeriN = 0; // br na menadzeri

        for ( int i = 0; i < N; i++ ){

            String str = br.readLine();
            String []par = str.split( " " );

            LinkedList<String> list = new LinkedList<>(); // pravi lista vo koja go stava momentalniot vraboten na menadzerot
            list.add( par[0] );

            SLLNode< MapEntry< String, LinkedList<String> > > mEntry = hash.search( par[1] ); // kofickata na menadzerot i

            if ( mEntry == null ) { // ako ne postoi koficka so ovoj menadzer i, pravam
                hash.insert(par[1], list);
                menadzeri[ menadzeriN++ ] = par[1];
            }

            else{ // ako postoi vo listata na negovi vraboteni( na menadzerot i ) go dodavam vraboteniot
                list = mEntry.element.value;
                list.add( par[0] );
            }

        }

        for ( int i = 0; i < menadzeriN; i++){ // ja iteriram nizata od menadzeri
                boolean vrabotenE = false;

            for ( int k = 0; k < menadzeriN; k++ ){ // povtorno ja iteriram nizata od menadzeri
                LinkedList<String> list = hash.search( menadzeri[k] ).element.value; // listata od vraboteni na menadzerot k( pominuva za site menadzeri vo hashot)

                for ( int j = 0; j < list.size(); j++ ){ // gi iteriram site iminja vo lstata

                    if( list.get( j ).equals( menadzeri[i] ) ){ // ako go najdam imeto na menadzerot, znaci deka e nekade vraboten
                        vrabotenE = true;
                        break;
                    }
                }
            }

            if( vrabotenE ){ //ako menadzerot e vraboten vo firmata

                LinkedList<String> giMenadzira = hash.search( menadzeri[i] ).element.value; // vrabotenite na mendzer i
                int num = 0; // br na vrabotemi
                for( int j = 0; j < giMenadzira.size(); j++ ){ // gi iterira vrabotenite
                    String str = giMenadzira.get( j );

                    if( !str.equals( menadzeri[i] ) ){ // ako se najde samiot sebe vo svoite vraboteni, ne se broi
                        num++;
                    }
                }
                System.out.print(  menadzeri[ i ] + "=" + num + ", " );
            }
        }

       //System.out.println( hash.toString() );
    }
}