[АПС] Лаб 9: Вовед во графови Социјална мрежа

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

public class CountFacebookFriends {

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

        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

        int howManyUsers = Integer.parseInt(bf.readLine());
        Integer[] nodeInfo = new Integer[howManyUsers];
        for(int i=0;i<howManyUsers;i++)
            nodeInfo[i] = i;
        Graph<Integer> users = new Graph<>(howManyUsers, nodeInfo);

        for(int i=0;i<howManyUsers;i++) {
            int howManyFriends = Integer.parseInt(bf.readLine());
            for(int j=0;j<howManyFriends;j++) {
                int y = Integer.parseInt(bf.readLine().split(" ")[0]);
                users.addEdge(i, y);
            }
        }

        int from = Integer.parseInt(bf.readLine());
        int to = Integer.parseInt(bf.readLine());

        users.bfs(from,to);

    }

}

class GraphNode<E> {
    private int index;//index (reden broj) na temeto vo grafot
    private E info;
    private LinkedList<GraphNode<E>> neighbors;

    public GraphNode(int index, E info) {
        this.index = index;
        this.info = info;
        neighbors = new LinkedList<GraphNode<E>>();
    }

    boolean containsNeighbor(GraphNode<E> o){
        return neighbors.contains(o);
    }

    void addNeighbor(GraphNode<E> o){
        neighbors.add(o);
    }

    void removeNeighbor(GraphNode<E> o){
        if(neighbors.contains(o))
            neighbors.remove(o);
    }

    @Override
    public String toString() {
        String ret= "INFO:"+info+" SOSEDI:";
        for(int i=0;i<neighbors.size();i++)
        ret+=neighbors.get(i).info+" ";
        return ret;

    }

    @Override
    public boolean equals(Object obj) {
        @SuppressWarnings("unchecked")
        GraphNode<E> pom = (GraphNode<E>)obj;
        return (pom.info.equals(this.info));
    }

    public int getIndex() {
        return index;
    }

    public void setIndex(int index) {
        this.index = index;
    }

    public E getInfo() {
        return info;
    }

    public void setInfo(E info) {
        this.info = info;
    }

    public LinkedList<GraphNode<E>> getNeighbors() {
        return neighbors;
    }

    public void setNeighbors(LinkedList<GraphNode<E>> neighbors) {
        this.neighbors = neighbors;
    }
}

class Graph<E> {

    int num_nodes;
    GraphNode<E> adjList[];

    @SuppressWarnings("unchecked")
    public Graph(int num_nodes, E[] list) {
        this.num_nodes = num_nodes;
        adjList = (GraphNode<E>[]) new GraphNode[num_nodes];
        for (int i = 0; i < num_nodes; i++)
            adjList[i] = new GraphNode<E>(i, list[i]);
    }

    @SuppressWarnings("unchecked")
    public Graph(int num_nodes) {
        this.num_nodes = num_nodes;
        adjList = (GraphNode<E>[]) new GraphNode[num_nodes];
    }

    boolean adjacent(int x, int y) {
        // proveruva dali ima vrska od jazelot so
        // indeks x do jazelot so indeks y
        return adjList[x].containsNeighbor(adjList[y]);
    }

    void addEdge(int x, int y) {
        // dodava vrska od jazelot so indeks x do jazelot so indeks y
        if (!adjList[x].containsNeighbor(adjList[y])) {
            adjList[x].addNeighbor(adjList[y]);
        }
        if(!adjList[y].containsNeighbor(adjList[x])) {
            adjList[y].addNeighbor(adjList[x]);
        }
    }

    void deleteEdge(int x, int y) {
        adjList[x].removeNeighbor(adjList[y]);
        adjList[y].removeNeighbor(adjList[x]);
    }

    void bfs(int from, int to){
        boolean visited[] = new boolean[num_nodes];
        for (int i = 0; i < num_nodes; i++)
            visited[i] = false;
        visited[from] = true;
        Queue<Integer> q = new LinkedList<Integer>();
        q.add(from);

        GraphNode<E> pom;

        int distance = 0;
        int parent = from;

        while(!q.isEmpty()){
            pom = adjList[q.poll()];
            if(pom.getIndex() == to)
                break;
            if(q.peek() == null || !this.adjacent(q.peek(), parent)) {
                // gledaj kako drvo, bfs na nekoj nacin grafot go pretvara vo drvo
                // koren = from, pa se dodeka ne se izminat site negovi deca, distance ne se zgolemuva
                // odnosno se dodeka ne naidesh vo redot na nekoj koj ne e sosed so navedeniot parent
                // ako toa se desi, stavi go parent da bide node - ot koj ne e sosed so prethodniot parent
                // zgolemi distance i prodolzi da proveruvash se dodeka vo redot ne stignesh do node == to
                distance++;
                parent = pom.getIndex();
            }
            GraphNode<E> tmp=null;
            for (int i = 0; i < pom.getNeighbors().size(); i++) {
                tmp = pom.getNeighbors().get(i);
                if (!visited[tmp.getIndex()]){
                    visited[tmp.getIndex()] = true;
                    q.add(tmp.getIndex());
                }
            }

        }
        System.out.println(distance);
    }


    @Override
    public String toString() {
        String ret = new String();
        for (int i = 0; i < this.num_nodes; i++)
            ret += i + ": " + adjList[i] + "\n";
        return ret;
    }

}