Kame3

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

Jan 19th, 2021
1,359
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. Компоненти на сврзаност Problem 10 (2 / 2)
  2.  
  3. За дадено теме да се прикажат сите темиња кои припаѓаат на иста компонента на сврзаност во даден граф. Темињата припаѓаат на иста компонента на сврзаност во графот доколку постои пат помеѓу нив. На влез прво се внесува бројот на темиња, потоа за секое теме се пишува бројот на темиња со кои е поврзано и индексите на темињата. На крај се внесува индексот на темето за кое ќе се бара решението.
  4.  
  5. Име на класата (Java): KomponentiSvrzanost.
  6.  
  7.  
  8. import java.io.BufferedReader;
  9. import java.io.InputStreamReader;
  10. import java.util.NoSuchElementException;
  11. import java.util.LinkedList;
  12. import java.util.Stack;
  13.  
  14. class SLLNode<E> {
  15.     protected E element;
  16.     protected SLLNode<E> succ;
  17.  
  18.     public SLLNode(E elem, SLLNode<E> succ) {
  19.         this.element = elem;
  20.         this.succ = succ;
  21.     }
  22.  
  23.     @Override
  24.     public String toString() {
  25.         return element.toString();
  26.     }
  27. }
  28.  
  29. // Implementacija na redica
  30.  
  31. interface Queue<E> {
  32.  
  33.     // Elementi na redicata se objekti od proizvolen tip.
  34.  
  35.     // Metodi za pristap:
  36.  
  37.     public boolean isEmpty ();
  38.         // Vrakja true ako i samo ako redicata e prazena.
  39.  
  40.     public int size ();
  41.         // Ja vrakja dolzinata na redicata.
  42.  
  43.     public E peek ();
  44.         // Go vrakja elementot na vrvot t.e. pocetokot od redicata.
  45.  
  46.     // Metodi za transformacija:
  47.  
  48.     public void clear ();
  49.         // Ja prazni redicata.
  50.  
  51.     public void enqueue (E x);
  52.         // Go dodava x na kraj od redicata.
  53.  
  54.     public E dequeue ();
  55.         // Go otstranuva i vrakja pochetniot element na redicata.
  56.  
  57. }
  58.  
  59. class LinkedQueue<E> implements Queue<E> {
  60.  
  61.     // Redicata e pretstavena na sledniot nacin:
  62.     // length go sodrzi brojot na elementi.
  63.     // Elementite se zachuvuvaat vo jazli dod SLL
  64.     // front i rear se linkovi do prviot i posledniot jazel soodvetno.
  65.     SLLNode<E> front, rear;
  66.     int length;
  67.  
  68.     // Konstruktor ...
  69.  
  70.     public LinkedQueue () {
  71.         clear();
  72.     }
  73.  
  74.     public boolean isEmpty () {
  75.         // Vrakja true ako i samo ako redicata e prazena.
  76.         return (length == 0);
  77.     }
  78.  
  79.     public int size () {
  80.         // Ja vrakja dolzinata na redicata.
  81.         return length;
  82.     }
  83.  
  84.     public E peek () {
  85.         // Go vrakja elementot na vrvot t.e. pocetokot od redicata.
  86.         if (front == null)
  87.             throw new NoSuchElementException();
  88.         return front.element;
  89.     }
  90.  
  91.     public void clear () {
  92.         // Ja prazni redicata.
  93.         front = rear = null;
  94.         length = 0;
  95.     }
  96.  
  97.     public void enqueue (E x) {
  98.         // Go dodava x na kraj od redicata.
  99.         SLLNode<E> latest = new SLLNode<E>(x, null);
  100.         if (rear != null) {
  101.             rear.succ = latest;
  102.             rear = latest;
  103.         } else
  104.             front = rear = latest;
  105.         length++;
  106.     }
  107.  
  108.     public E dequeue () {
  109.         // Go otstranuva i vrakja pochetniot element na redicata.
  110.         if (front != null) {
  111.             E frontmost = front.element;
  112.             front = front.succ;
  113.             if (front == null)  rear = null;
  114.             length--;
  115.             return frontmost;
  116.         } else
  117.             throw new NoSuchElementException();
  118.     }
  119.  
  120. }
  121.  
  122. class GraphNode<E> {
  123.     private int index;//index (reden broj) na temeto vo grafot
  124.     private E ime;
  125.     private E prezime;
  126.     private LinkedList<GraphNode<E>> neighbors;
  127.    
  128.     public GraphNode(int index, E ime, E prezime) {
  129.         this.index = index;
  130.         this.ime = ime;
  131.         this.prezime = prezime;
  132.         neighbors = new LinkedList<GraphNode<E>>();
  133.     }
  134.    
  135.     public GraphNode(int index) {
  136.         this.index = index;
  137.        
  138.         neighbors = new LinkedList<GraphNode<E>>();
  139.     }
  140.    
  141.     boolean containsNeighbor(GraphNode<E> o){
  142.         return neighbors.contains(o);
  143.     }
  144.    
  145.     void addNeighbor(GraphNode<E> o){
  146.         neighbors.add(o);
  147.     }
  148.    
  149.     void removeNeighbor(GraphNode<E> o){
  150.         if(neighbors.contains(o))
  151.             neighbors.remove(o);
  152.     }
  153.  
  154.    
  155.  
  156.     public int getIndex() {
  157.         return index;
  158.     }
  159.  
  160.     public void setIndex(int index) {
  161.         this.index = index;
  162.     }
  163.  
  164.    
  165.  
  166.  
  167.     public LinkedList<GraphNode<E>> getNeighbors() {
  168.         return neighbors;
  169.     }
  170.  
  171.     public void setNeighbors(LinkedList<GraphNode<E>> neighbors) {
  172.         this.neighbors = neighbors;
  173.     }
  174. }
  175.  
  176. class Graph<E> {
  177.  
  178.     int num_nodes;
  179.     GraphNode<E> adjList[];
  180.  
  181.    
  182.  
  183.     @SuppressWarnings("unchecked")
  184.     public Graph(int num_nodes) {
  185.         this.num_nodes = num_nodes;
  186.         adjList = (GraphNode<E>[]) new GraphNode[num_nodes];
  187.         for (int i = 0; i < num_nodes; i++)
  188.             adjList[i] = new GraphNode<E>(i);
  189.     }
  190.  
  191.     int adjacent(int x, int y) {
  192.         // proveruva dali ima vrska od jazelot so
  193.         // indeks x do jazelot so indeks y
  194.         return (adjList[x].containsNeighbor(adjList[y])) ? 1 : 0;
  195.     }
  196.  
  197.     void addEdge(int x, int y) {
  198.         // dodava vrska od jazelot so indeks x do jazelot so indeks y
  199.         if (!adjList[x].containsNeighbor(adjList[y])) {
  200.             adjList[x].addNeighbor(adjList[y]);
  201.         }
  202.     }
  203.  
  204.     void deleteEdge(int x, int y) {
  205.         adjList[x].removeNeighbor(adjList[y]);
  206.     }
  207.    
  208.     void dfsVisit(boolean[] visited, int node, Stack<Integer> s){
  209.         if(!visited[node]){
  210.             visited[node] = true;
  211.             s.push(node);
  212.             LinkedList<GraphNode<E>> neighbors = adjList[node].getNeighbors();
  213.             for(GraphNode<E> i : neighbors){
  214.                 if(!visited[i.getIndex()]&&adjacent(i.getIndex(),node) == 1)
  215.                     dfsVisit(visited,i.getIndex(),s);
  216.             }
  217.         }
  218.     }
  219.    
  220.     int [] najdikomponenti(int start){
  221.      
  222.         //vasiot kod tuka
  223.         boolean[] visited = new boolean[num_nodes];
  224.         for(int i=0;i<num_nodes;i++){
  225.             visited[i] = false;
  226.         }
  227.         Stack<Integer> s = new Stack<Integer>();
  228.         visited[start] = true;
  229.         LinkedList<GraphNode<E>> sosedi = this.adjList[start].getNeighbors(); //sosedite na pocetnoto teme
  230.         for(GraphNode<E> n : sosedi){
  231.             if(adjacent(n.getIndex(),start) == 1){
  232.                 if(!visited[n.getIndex()])
  233.                     dfsVisit(visited,n.getIndex(),s);
  234.             }
  235.         }
  236.        
  237.         int n = s.size();
  238.         int arr[] = new int[n+1];
  239.        
  240.         s.push(start);
  241.         for(int i=0;i<= n;i++){
  242.             arr[i] = s.pop();
  243.         }
  244.         return arr;
  245.     }
  246.    
  247.  
  248.     @Override
  249.     public String toString() {
  250.         String ret = new String();
  251.         for (int i = 0; i < this.num_nodes; i++)
  252.             ret += i + ": " + adjList[i] + "\n";
  253.         return ret;
  254.     }
  255.  
  256. }
  257.  
  258.  
  259. public class KomponentiSvrzanost {
  260.    
  261.     public static void bubbleSort(int[] arr){
  262.         for(int i=0;i<arr.length-1;i++){
  263.             for(int j=0;j<arr.length-i-1;j++){
  264.                 if(arr[j] > arr[j+1]){
  265.                     int tmp = arr[j];
  266.                     arr[j] = arr[j+1];
  267.                     arr[j+1] = tmp;
  268.                 }
  269.             }
  270.         }
  271.     }
  272.    
  273.     public static void main(String[] args) throws Exception {
  274.         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  275.         int N = Integer.parseInt(br.readLine());
  276.        
  277.        
  278.         Graph<String> g = new Graph<String>(N);
  279.        
  280.         int sosedIndex;
  281.         int i_num_nodes;
  282.         String pom;
  283.         for(int i=0;i<N;i++)
  284.         {
  285.             i_num_nodes = Integer.parseInt(br.readLine());
  286.             for(int j=0;j<i_num_nodes;j++)
  287.             {
  288.                 pom = br.readLine();
  289.                 sosedIndex = Integer.parseInt(pom);
  290.            
  291.                 g.addEdge(i,sosedIndex);                  
  292.             }
  293.         }      
  294.        
  295.        
  296.         int teme = Integer.parseInt(br.readLine());
  297.        int[] komponenti =g.najdikomponenti(teme);
  298.       //vasiot kod tuka
  299.         bubbleSort(komponenti);
  300.         for(int i=0;i<komponenti.length;i++){
  301.             System.out.println(komponenti[i]);
  302.         }
  303.        
  304.        
  305.         br.close();
  306.     }
  307.  
  308. }
  309.  
  310.  
  311.  
  312. Sample input
  313.  
  314. 8
  315. 1
  316. 5
  317. 2
  318. 2
  319. 6
  320. 2
  321. 1
  322. 3
  323. 2
  324. 2
  325. 6
  326. 2
  327. 5
  328. 7
  329. 2
  330. 4
  331. 7
  332. 2
  333. 3
  334. 1
  335. 2
  336. 4
  337. 5
  338. 7
  339.  
  340. Sample output
  341.  
  342. 4
  343. 5
  344. 7
  345.  
  346.  
RAW Paste Data