mvCode

KomponentiSvrzanost AIPS Компоненти на сврзаност

Jan 19th, 2020
47
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 6.89 KB | None | 0 0
  1. import java.io.BufferedReader;
  2. import java.io.InputStreamReader;
  3. import java.util.NoSuchElementException;
  4. import java.util.LinkedList;
  5.  
  6. class SLLNode<E> {
  7.     protected E element;
  8.     protected SLLNode<E> succ;
  9.  
  10.     public SLLNode(E elem, SLLNode<E> succ) {
  11.         this.element = elem;
  12.         this.succ = succ;
  13.     }
  14.  
  15.     @Override
  16.     public String toString() {
  17.         return element.toString();
  18.     }
  19. }
  20.  
  21. // Implementacija na redica
  22.  
  23. interface Queue<E> {
  24.  
  25.     // Elementi na redicata se objekti od proizvolen tip.
  26.  
  27.     // Metodi za pristap:
  28.  
  29.     public boolean isEmpty ();
  30.     // Vrakja true ako i samo ako redicata e prazena.
  31.  
  32.     public int size ();
  33.     // Ja vrakja dolzinata na redicata.
  34.  
  35.     public E peek ();
  36.     // Go vrakja elementot na vrvot t.e. pocetokot od redicata.
  37.  
  38.     // Metodi za transformacija:
  39.  
  40.     public void clear ();
  41.     // Ja prazni redicata.
  42.  
  43.     public void enqueue (E x);
  44.     // Go dodava x na kraj od redicata.
  45.  
  46.     public E dequeue ();
  47.     // Go otstranuva i vrakja pochetniot element na redicata.
  48.  
  49. }
  50.  
  51. class LinkedQueue<E> implements Queue<E> {
  52.  
  53.     // Redicata e pretstavena na sledniot nacin:
  54.     // length go sodrzi brojot na elementi.
  55.     // Elementite se zachuvuvaat vo jazli dod SLL
  56.     // front i rear se linkovi do prviot i posledniot jazel soodvetno.
  57.     SLLNode<E> front, rear;
  58.     int length;
  59.  
  60.     // Konstruktor ...
  61.  
  62.     public LinkedQueue () {
  63.         clear();
  64.     }
  65.  
  66.     public boolean isEmpty () {
  67.         // Vrakja true ako i samo ako redicata e prazena.
  68.         return (length == 0);
  69.     }
  70.  
  71.     public int size () {
  72.         // Ja vrakja dolzinata na redicata.
  73.         return length;
  74.     }
  75.  
  76.     public E peek () {
  77.         // Go vrakja elementot na vrvot t.e. pocetokot od redicata.
  78.         if (front == null)
  79.             throw new NoSuchElementException();
  80.         return front.element;
  81.     }
  82.  
  83.     public void clear () {
  84.         // Ja prazni redicata.
  85.         front = rear = null;
  86.         length = 0;
  87.     }
  88.  
  89.     public void enqueue (E x) {
  90.         // Go dodava x na kraj od redicata.
  91.         SLLNode<E> latest = new SLLNode<E>(x, null);
  92.         if (rear != null) {
  93.             rear.succ = latest;
  94.             rear = latest;
  95.         } else
  96.             front = rear = latest;
  97.         length++;
  98.     }
  99.  
  100.     public E dequeue () {
  101.         // Go otstranuva i vrakja pochetniot element na redicata.
  102.         if (front != null) {
  103.             E frontmost = front.element;
  104.             front = front.succ;
  105.             if (front == null)  rear = null;
  106.             length--;
  107.             return frontmost;
  108.         } else
  109.             throw new NoSuchElementException();
  110.     }
  111.  
  112. }
  113.  
  114. class GraphNode<E> {
  115.     private int index;//index (reden broj) na temeto vo grafot
  116.     private E ime;
  117.     private E prezime;
  118.     private LinkedList<GraphNode<E>> neighbors;
  119.  
  120.     public GraphNode(int index, E ime, E prezime) {
  121.         this.index = index;
  122.         this.ime = ime;
  123.         this.prezime = prezime;
  124.         neighbors = new LinkedList<GraphNode<E>>();
  125.     }
  126.  
  127.     public GraphNode(int index) {
  128.         this.index = index;
  129.  
  130.         neighbors = new LinkedList<GraphNode<E>>();
  131.     }
  132.  
  133.     boolean containsNeighbor(GraphNode<E> o) {
  134.         return neighbors.contains(o);
  135.     }
  136.  
  137.     void addNeighbor(GraphNode<E> o) {
  138.         neighbors.add(o);
  139.     }
  140.  
  141.     void removeNeighbor(GraphNode<E> o) {
  142.         if(neighbors.contains(o))
  143.             neighbors.remove(o);
  144.     }
  145.  
  146.  
  147.  
  148.     public int getIndex() {
  149.         return index;
  150.     }
  151.  
  152.     public void setIndex(int index) {
  153.         this.index = index;
  154.     }
  155.  
  156.  
  157.  
  158.  
  159.     public LinkedList<GraphNode<E>> getNeighbors() {
  160.         return neighbors;
  161.     }
  162.  
  163.     public void setNeighbors(LinkedList<GraphNode<E>> neighbors) {
  164.         this.neighbors = neighbors;
  165.     }
  166. }
  167.  
  168. class Graph<E> {
  169.  
  170.     int num_nodes;
  171.     GraphNode<E> adjList[];
  172.  
  173.  
  174.  
  175.     @SuppressWarnings("unchecked")
  176.     public Graph(int num_nodes) {
  177.         this.num_nodes = num_nodes;
  178.         adjList = (GraphNode<E>[]) new GraphNode[num_nodes];
  179.         for (int i = 0; i < num_nodes; i++)
  180.             adjList[i] = new GraphNode<E>(i);
  181.     }
  182.  
  183.     int adjacent(int x, int y) {
  184.         // proveruva dali ima vrska od jazelot so
  185.         // indeks x do jazelot so indeks y
  186.         return (adjList[x].containsNeighbor(adjList[y])) ? 1 : 0;
  187.     }
  188.  
  189.     void addEdge(int x, int y) {
  190.         // dodava vrska od jazelot so indeks x do jazelot so indeks y
  191.         if (!adjList[x].containsNeighbor(adjList[y])) {
  192.             adjList[x].addNeighbor(adjList[y]);
  193.         }
  194.     }
  195.  
  196.     void deleteEdge(int x, int y) {
  197.         adjList[x].removeNeighbor(adjList[y]);
  198.     }
  199.  
  200.     int [] najdikomponenti(int start) {
  201.  
  202.         //vasiot kod tuka
  203.         LinkedQueue< Integer > queue = new LinkedQueue<>();
  204.         int []komponenti = new int[100];
  205.         for ( int i = 0; i < 100; i++) {
  206.             komponenti[i] = -1;
  207.         }
  208.  
  209.         queue.enqueue( start );
  210.         komponenti[start] = 1;
  211.         int pom;
  212.  
  213.         while ( !queue.isEmpty() ) {
  214.             pom = queue.dequeue();
  215.             GraphNode< E > node = adjList[ pom ]; // od listata vo grafot go zimam momentalniot node( so indeks pom )
  216.             LinkedList< GraphNode<E> > list = node.getNeighbors(); // lista na sosedi na node( pom )
  217.  
  218.             for ( int i = 0; i < list.size(); i++ ) { // ja iteriram listat na sosedi na pom
  219.                 GraphNode< E > neighbor = list.get( i );
  220.                 int index = neighbor.getIndex(); // indeks na sosedot i
  221.                 if( komponenti[index] != 1 ) {
  222.                     queue.enqueue( index );
  223.                     komponenti[index] = 1;
  224.                 }
  225.             }
  226.         }
  227.         return komponenti;
  228.     }
  229.  
  230.  
  231.     @Override
  232.     public String toString() {
  233.         String ret = new String();
  234.         for (int i = 0; i < this.num_nodes; i++)
  235.             ret += i + ": " + adjList[i] + "\n";
  236.         return ret;
  237.     }
  238.  
  239. }
  240.  
  241.  
  242. public class KomponentiSvrzanost {
  243.  
  244.     public static void main(String[] args) throws Exception {
  245.         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  246.         int N = Integer.parseInt(br.readLine());
  247.  
  248.  
  249.         Graph<String> g = new Graph<String>(N);
  250.  
  251.         int sosedIndex;
  252.         int i_num_nodes;
  253.         String pom;
  254.         for(int i=0; i<N; i++) {
  255.             i_num_nodes = Integer.parseInt(br.readLine());
  256.             for(int j=0; j<i_num_nodes; j++) {
  257.                 pom = br.readLine();
  258.                 sosedIndex = Integer.parseInt(pom);
  259.  
  260.                 g.addEdge(i,sosedIndex);
  261.             }
  262.         }
  263.  
  264.  
  265.         int teme = Integer.parseInt(br.readLine());
  266.         int[] komponenti =g.najdikomponenti(teme);
  267.         //vasiot kod tuka
  268.         for ( int i = 0; i < komponenti.length; i++ ) {
  269.             if( komponenti[i] == 1 )
  270.                 System.out.println( i );
  271.         }
  272.  
  273.         br.close();
  274.     }
  275.  
  276. }
Add Comment
Please, Sign In to add comment