Kame3

Вкупен број на патишта - [граф]

Jan 19th, 2021 (edited)
483
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. Вкупен број на патишта Problem 7 (0 / 0)
  2.  
  3. Да се испечати вкупниот број на патишта со должина N кои почнуваат од некое фиксно теме V во неориентиран нетежински граф.
  4.  
  5. Влез: Во првиот ред е даден бројот на јазли, во вториот ред е даден бројот на ребра, а потоа во следните редови се дадени ребрата во графот. Во претпоследниот ред се дадени темето V и во последниот ред, должината N на патиштата.
  6.  
  7. Излез: Испечатете го вкупниот број на патишта со должина N. Јазлите во патот можат да се повторуваат.
  8.  
  9. Во дадениот пример, постојат два пата 0 1 2 и 0 1 0, кои почнуваат од јазолот 0 и имаат должина 2.
  10.  
  11. Име на класата (Java): PathCount.
  12.  
  13.  
  14. import java.io.BufferedReader;
  15. import java.io.InputStreamReader;
  16. import java.util.LinkedList;
  17.  
  18.  
  19. class Graph<E> {
  20.  
  21.     int num_nodes; // broj na jazli
  22.     E nodes[]; // informacija vo jazlite - moze i ne mora?
  23.     int adjMat[][]; // matrica na sosednost
  24.  
  25.     @SuppressWarnings("unchecked")
  26.     public Graph(int num_nodes) {
  27.         this.num_nodes = num_nodes;
  28.         nodes = (E[]) new Object[num_nodes];
  29.         adjMat = new int[num_nodes][num_nodes];
  30.  
  31.         for (int i = 0; i < this.num_nodes; i++)
  32.             for (int j = 0; j < this.num_nodes; j++)
  33.                 adjMat[i][j] = 0;
  34.     }
  35.  
  36.     int adjacent(int x, int y) { // proveruva dali ima vrska od jazelot so
  37.                                     // indeks x do jazelot so indeks y
  38.         return (adjMat[x][y] != 0) ? 1 : 0;
  39.     }
  40.  
  41.     void addEdge(int x, int y) { // dodava vrska megu jazlite so indeksi x i y
  42.         adjMat[x][y] = 1;
  43.         adjMat[y][x] = 1;
  44.     }
  45.  
  46.     void deleteEdge(int x, int y) {
  47.         // ja brise vrskata megu jazlite so indeksi x i y
  48.         adjMat[x][y] = 0;
  49.         adjMat[y][x] = 0;
  50.     }
  51.  
  52.     E get_node_value(int x) { // ja vraka informacijata vo jazelot so indeks x
  53.         return nodes[x];
  54.     }
  55.  
  56.     void set_node_value(int x, E a) { // ja postavuva informacijata vo jazelot
  57.                                         // so indeks na a
  58.         nodes[x] = a;
  59.     }
  60.  
  61.     @Override
  62.     public String toString() {
  63.         String ret = "  ";
  64.         for (int i = 0; i < num_nodes; i++)
  65.             ret += nodes[i] + " ";
  66.         ret += "\n";
  67.         for (int i = 0; i < num_nodes; i++) {
  68.             ret += nodes[i] + " ";
  69.             for (int j = 0; j < num_nodes; j++)
  70.                 ret += adjMat[i][j] + " ";
  71.             ret += "\n";
  72.         }
  73.         return ret;
  74.     }
  75.  
  76.     public void printMatrix() {
  77.         for (int i = 0; i < num_nodes; i++) {
  78.             for (int j = 0; j < num_nodes; j++)
  79.                 System.out.print(adjMat[i][j] + " ");
  80.             System.out.println();
  81.         }
  82.     }
  83.    
  84.     public int pathCount(int nodeIndex,int pathLength){
  85.         //vasiot kod tuka
  86.         LinkedList<Integer> first = new LinkedList<>();
  87.         LinkedList<Integer> second = new LinkedList<>();
  88.        
  89.         first.add(nodeIndex);
  90.        
  91.         for(int i=0;i<pathLength;i++){
  92.             second = new LinkedList<>();
  93.             while(!first.isEmpty()){
  94.                 int x = first.remove();
  95.                 for(int j=0;j<num_nodes;j++){ // gi vrtime jazlite
  96.                     if(adjMat[x][j] == 1) // ako ima rebro pomegju x i ostanatite
  97.                         second.add(j); // dodadi gi vo listata
  98.                 }
  99.             }
  100.             first = (LinkedList<Integer>) second.clone();
  101.         }
  102.         return second.size();
  103.        
  104.     }
  105.  
  106. }
  107.  
  108. public class PathCount {
  109.  
  110.     public static void main(String[] args) throws Exception {
  111.         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  112.         int N = Integer.parseInt(br.readLine());
  113.         Graph<Integer> g=new Graph<>(N);
  114.         int M = Integer.parseInt(br.readLine());
  115.         for (int i=0;i<M;i++){
  116.             String line=br.readLine();
  117.             String edgeLine[]=line.split(" ");
  118.             g.addEdge(Integer.parseInt(edgeLine[0]), Integer.parseInt(edgeLine[1]));
  119.         }
  120.         int nodeIndex=Integer.parseInt(br.readLine());
  121.         int pathLength=Integer.parseInt(br.readLine());
  122.         System.out.println(g.pathCount(nodeIndex, pathLength));
  123.         br.close();
  124.  
  125.     }
  126.  
  127. }
  128.  
  129.  
  130.  
  131. Sample input
  132.  
  133. 6
  134. 5
  135. 0 1
  136. 1 2
  137. 2 3
  138. 3 4
  139. 4 5
  140. 1
  141. 4
  142.  
  143. Sample output
  144.  
  145. 10
  146.  
  147.  
RAW Paste Data