Компоненти на сврзаност - [граф]

Компоненти на сврзаност Problem 10 (2 / 2)

За дадено теме да се прикажат сите темиња кои припаѓаат на иста компонента на сврзаност во даден граф. Темињата припаѓаат на иста компонента на сврзаност во графот доколку постои пат помеѓу нив. На влез прво се внесува бројот на темиња, потоа за секое теме се пишува бројот на темиња со кои е поврзано и индексите на темињата. На крај се внесува индексот на темето за кое ќе се бара решението.

Име на класата (Java): KomponentiSvrzanost.


import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.NoSuchElementException;
import java.util.LinkedList;
import java.util.Stack;

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

// Implementacija na redica

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

}

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

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

    public GraphNode(int index) {
        this.index = index;

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



    public int getIndex() {
        return index;
    }

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




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

    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 dfsVisit(boolean[] visited, int node, Stack<Integer> s){
        if(!visited[node]){
            visited[node] = true;
            s.push(node);
            LinkedList<GraphNode<E>> neighbors = adjList[node].getNeighbors();
            for(GraphNode<E> i : neighbors){
                if(!visited[i.getIndex()]&&adjacent(i.getIndex(),node) == 1)
                    dfsVisit(visited,i.getIndex(),s);
            }
        }
    }

    int [] najdikomponenti(int start){

        //vasiot kod tuka
        boolean[] visited = new boolean[num_nodes];
        for(int i=0;i<num_nodes;i++){
            visited[i] = false;
        }
        Stack<Integer> s = new Stack<Integer>();
        visited[start] = true;
        LinkedList<GraphNode<E>> sosedi = this.adjList[start].getNeighbors(); //sosedite na pocetnoto teme
        for(GraphNode<E> n : sosedi){
            if(adjacent(n.getIndex(),start) == 1){
                if(!visited[n.getIndex()])
                    dfsVisit(visited,n.getIndex(),s);
            }
        }

        int n = s.size();
        int arr[] = new int[n+1];

        s.push(start);
        for(int i=0;i<= n;i++){
            arr[i] = s.pop();
        }
        return arr;
    }


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

}


public class KomponentiSvrzanost {

    public static void bubbleSort(int[] arr){
        for(int i=0;i<arr.length-1;i++){
            for(int j=0;j<arr.length-i-1;j++){
                if(arr[j] > arr[j+1]){
                    int tmp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = tmp;
                }
            }
        }
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());


        Graph<String> g = new Graph<String>(N);

        int sosedIndex;
        int i_num_nodes;
        String pom;
        for(int i=0;i<N;i++)
        {
            i_num_nodes = Integer.parseInt(br.readLine());
            for(int j=0;j<i_num_nodes;j++)
            {
                pom = br.readLine();
                sosedIndex = Integer.parseInt(pom);

                g.addEdge(i,sosedIndex);
            }
        }


        int teme = Integer.parseInt(br.readLine());
       int[] komponenti =g.najdikomponenti(teme);
      //vasiot kod tuka
        bubbleSort(komponenti);
        for(int i=0;i<komponenti.length;i++){
            System.out.println(komponenti[i]);
        }


        br.close();
    }

}



Sample input

8
1
5
2
2
6
2
1
3
2
2
6
2
5
7
2
4
7
2
3
1
2
4
5
7

Sample output

4
5
7