Социјална мрежа lab9.3

Социјална мрежа Problem 3 (0 / 0)

Дадена е една социјална мрежа (Facebook) во која за корисниците се чуваат податоци за реден број (целобројна вредност), име и презиме. Исто така, за секој корисник познати се неговите пријатели во социјалната мрежа. Да се напише алгоритам кој за дадени редни броеви на двајца корисници го одредува степенот на разделеност помеѓу корисниците т.е. преку колку најмалку корисници се поврзани (преку колку најмалку корисници може да се стигне од едниот до другиот корисник) во социјалната мрежа. Социјалната мрежа е претставена како нетежински граф со листа на соседство. Во првиот ред од влезот е даден бројот на корисниците. Потоа, во следниот ред е даден бројот на пријателите на првиот корисник (со реден број 0), и во следните редови се наведени неговите пријатели со реден број, име и презиме. Понатаму се дадени на истиот начин информациите за сите корисници. На крај во последните два реда се дадени редните броеви на двата корисници за кои треба да се одреди степенот на разделеност.

Име на класата: CountFacebookFriends


import java.util.Scanner;
import java.util.LinkedList;
import java.util.Iterator;
import java.util.Stack;
import java.util.NoSuchElementException;
import java.io.IOException;
import java.io.InputStreamReader;

public class CountFacebookFriends {


    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();

        GraphNode<User>[] niza = new GraphNode[n];
        int mat[][] = new int[n][n];

        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                mat[i][j] = 0;

        for (int i = 0; i < n; i++) {
            int friends = in.nextInt();

            for (int j = 0; j < friends; j++) {
                int index = in.nextInt();
                String name = in.next();
                String lastname = in.next();


                User user = new User(index, name, lastname);

                mat[i][index] = 1;
                mat[index][i] = 1;

                GraphNode<User> pom = new GraphNode<User>(index, user);
                niza[index] = pom;
            }
        }

        Graph g = new Graph(n, niza);

        for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) {
            if (mat[i][j] == 1) {
                g.addEdge(i, j);
            }
        }

        int a = in.nextInt();
        int b = in.nextInt();

        if (a == b){
            System.out.println("0");
            return;
        }

        int dist[] = new int[n];
        boolean visited[] = new boolean[n];

        for (int i = 0; i < n; i++) {
            visited[i] = false;
            dist[i] = 0;
        }


        visited[a] = true;

        Queue<Integer> q = new LinkedQueue<Integer>();
        q.enqueue(a);

        while (!q.isEmpty()) {
            int pom = q.dequeue();

            for (int i = 0; i < n; i++) {
                if (g.adjacent(pom, i) == 1) {
                    if (!visited[i]) {
                        visited[i] = true;
                        dist[i] = dist[pom] + 1;
                        q.enqueue(i);

                        if (i == b) {
                            System.out.print(dist[i]);
                            return;
                        }
                    }
                }
            }
        }

    }
}

class User {
    int index;
    String name, lastname;

    public User(int index, String name, String lastname) {
        this.index = index;
        this.name = name;
        this.lastname = lastname;
    }

    @Override
    public String toString() {
        return index +", " + name + ", " + lastname;

    }
}

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];
    }

    int 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])) ? 1 : 0;
    }

    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]);
        }
    }

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

    void dfsSearch(int node) {
        boolean visited[] = new boolean[num_nodes];
        for (int i = 0; i < num_nodes; i++)
            visited[i] = false;
        dfsRecursive(node, visited);
    }

    void dfsRecursive(int node, boolean visited[]) {
        visited[node] = true;
        System.out.println(node + ": " + adjList[node].getInfo());

        for (int i = 0; i < adjList[node].getNeighbors().size(); i++) {
            GraphNode<E> pom = adjList[node].getNeighbors().get(i);
            if (!visited[pom.getIndex()])
                dfsRecursive(pom.getIndex(), visited);
        }
    }

    void dfsNonrecursive(int node) {
        boolean visited[] = new boolean[num_nodes];
        for (int i = 0; i < num_nodes; i++)
            visited[i] = false;
        visited[node] = true;
        System.out.println(node+": " + adjList[node].getInfo());
        Stack<Integer> s = new Stack<Integer>();
        s.push(node);

        GraphNode<E> pom;

        while (!s.isEmpty()) {
            pom = adjList[s.peek()];
            GraphNode<E> tmp=null;
            for (int i = 0; i < pom.getNeighbors().size(); i++) {
                tmp = pom.getNeighbors().get(i);
                if (!visited[tmp.getIndex()])
                    break;
            }
            if(tmp!=null&&!visited[tmp.getIndex()]){
                visited[tmp.getIndex()] = true;
                System.out.println(tmp.getIndex() + ": " + tmp.getInfo());
                s.push(tmp.getIndex());
            }
            else
                s.pop();
        }

    }

    void bfs(int node){
        boolean visited[] = new boolean[num_nodes];
        for (int i = 0; i < num_nodes; i++)
            visited[i] = false;
        visited[node] = true;
        System.out.println(node+": " + adjList[node].getInfo());
        Queue<Integer> q = new LinkedQueue<Integer>();
        q.enqueue(node);

        GraphNode<E> pom;

        while(!q.isEmpty()){
            pom = adjList[q.dequeue()];
            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;
                    System.out.println(tmp.getIndex()+": " + tmp.getInfo());
                    q.enqueue(tmp.getIndex());
                }
            }


        }

    }


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

}

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 LinkedQueue<E> implements Queue<E> {

    // Redicata e pretstavena na sledniot nacin:
    // length go sodrzi brojot na elementi.
    // Elementite se zachuvuvaat vo jazli dod SLL
    // front i rear se linkovi do prviot i posledniot jazel soodvetno.
    SLLNode<E> front, rear;
    int length;

    // Konstruktor ...

    public LinkedQueue () {
        clear();
    }

    public boolean isEmpty () {
        // Vrakja true ako i samo ako redicata e prazena.
        return (length == 0);
    }

    public int size () {
        // Ja vrakja dolzinata na redicata.
        return length;
    }

    public E peek () {
        // Go vrakja elementot na vrvot t.e. pocetokot od redicata.
        if (front == null)
            throw new NoSuchElementException();
        return front.element;
    }

    public void clear () {
        // Ja prazni redicata.
        front = rear = null;
        length = 0;
    }

    public void enqueue (E x) {
        // Go dodava x na kraj od redicata.
        SLLNode<E> latest = new SLLNode<E>(x, null);
        if (rear != null) {
            rear.succ = latest;
            rear = latest;
        } else
            front = rear = latest;
        length++;
    }

    public E dequeue () {
        // Go otstranuva i vrakja pochetniot element na redicata.
        if (front != null) {
            E frontmost = front.element;
            front = front.succ;
            if (front == null)  rear = null;
            length--;
            return frontmost;
        } else
            throw new NoSuchElementException();
    }

}

interface Queue<E> {

    // Elementi na redicata se objekti od proizvolen tip.

    // Metodi za pristap:

    public boolean isEmpty ();
        // Vrakja true ako i samo ako redicata e prazena.

    public int size ();
        // Ja vrakja dolzinata na redicata.

    public E peek ();
        // Go vrakja elementot na vrvot t.e. pocetokot od redicata.

    // Metodi za transformacija:

    public void clear ();
        // Ja prazni redicata.

    public void enqueue (E x);
        // Go dodava x na kraj od redicata.

    public E dequeue ();
        // Go otstranuva i vrakja pochetniot element na redicata.

}

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();
    }
}


Sample input

3
2
1 Ilinka Ivanoska
2 Igor Kulev
1
0 Magdalena Kostoska
1
0 Magdalena Kostoska
0
1

Sample output

1

Simple Input:
6
1
1 Ilinka Ivanoska
2
0 Magdalena Kostoska
2 Igor Kulev
2
1 Ilinka Ivanoska
3 Vladimir Trajkovik
2
2 Igor Kulev
4 Anastas Misev
2
3 Vladimir Trajkovik
5 Slobodan Kalajdziski
1
4 Anastas Misev
1
5


Simple Output:

4