mvCode

PathCount, Вкупен број на патишта, AIPS

Jan 19th, 2020
60
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 3.38 KB | None | 0 0
  1. import java.io.BufferedReader;
  2. import java.io.InputStreamReader;
  3.  
  4. class Graph<E> {
  5.  
  6.     int num_nodes; // broj na jazli
  7.     E nodes[]; // informacija vo jazlite - moze i ne mora?
  8.     int adjMat[][]; // matrica na sosednost
  9.  
  10.     @SuppressWarnings("unchecked")
  11.     public Graph(int num_nodes) {
  12.         this.num_nodes = num_nodes;
  13.         nodes = (E[]) new Object[num_nodes];
  14.         adjMat = new int[num_nodes][num_nodes];
  15.  
  16.         for (int i = 0; i < this.num_nodes; i++)
  17.             for (int j = 0; j < this.num_nodes; j++)
  18.                 adjMat[i][j] = 0;
  19.     }
  20.  
  21.     int adjacent(int x, int y) { // proveruva dali ima vrska od jazelot so
  22.         // indeks x do jazelot so indeks y
  23.         return (adjMat[x][y] != 0) ? 1 : 0;
  24.     }
  25.  
  26.     void addEdge(int x, int y) { // dodava vrska megu jazlite so indeksi x i y
  27.         adjMat[x][y] = 1;
  28.         adjMat[y][x] = 1;
  29.     }
  30.  
  31.     void deleteEdge(int x, int y) {
  32.         // ja brise vrskata megu jazlite so indeksi x i y
  33.         adjMat[x][y] = 0;
  34.         adjMat[y][x] = 0;
  35.     }
  36.  
  37.     E get_node_value(int x) { // ja vraka informacijata vo jazelot so indeks x
  38.         return nodes[x];
  39.     }
  40.  
  41.     void set_node_value(int x, E a) { // ja postavuva informacijata vo jazelot
  42.         // so indeks na a
  43.         nodes[x] = a;
  44.     }
  45.  
  46.     @Override
  47.     public String toString() {
  48.         String ret = "  ";
  49.         for (int i = 0; i < num_nodes; i++)
  50.             ret += nodes[i] + " ";
  51.         ret += "\n";
  52.         for (int i = 0; i < num_nodes; i++) {
  53.             ret += nodes[i] + " ";
  54.             for (int j = 0; j < num_nodes; j++)
  55.                 ret += adjMat[i][j] + " ";
  56.             ret += "\n";
  57.         }
  58.         return ret;
  59.     }
  60.  
  61.     public void printMatrix() {
  62.         for (int i = 0; i < num_nodes; i++) {
  63.             for (int j = 0; j < num_nodes; j++)
  64.                 System.out.print(adjMat[i][j] + " ");
  65.             System.out.println();
  66.         }
  67.     }
  68.  
  69.     public int pathCount(int nodeIndex,int pathLength) {
  70.         //vasiot kod tuka
  71.         return pathCount( nodeIndex, pathLength, 1 );
  72.     }
  73.  
  74.     public int pathCount(int nodeIndex, int pathLength, int lenght) {
  75.         //vasiot kod tuka
  76.         if( lenght == pathLength ) {
  77.             int adj = 0;
  78.             for (int i = 0; i < num_nodes; i++) {
  79.                 if (adjacent(nodeIndex, i) == 1)
  80.                     adj++;
  81.             }
  82.             return adj;
  83.         }
  84.         int adj = 0;
  85.         for (int i = 0; i < num_nodes; i++) {
  86.             if (adjacent(nodeIndex, i) == 1) {
  87.                 adj += pathCount(i, pathLength, lenght + 1);
  88.             }
  89.         }
  90.         return adj;
  91.     }
  92.  
  93. }
  94.  
  95. public class PathCount {
  96.  
  97.     public static void main(String[] args) throws Exception {
  98.         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  99.         int N = Integer.parseInt(br.readLine());
  100.         Graph<Integer> g=new Graph<>(N);
  101.         int M = Integer.parseInt(br.readLine());
  102.         for (int i=0; i<M; i++) {
  103.             String line=br.readLine();
  104.             String edgeLine[]=line.split(" ");
  105.             g.addEdge(Integer.parseInt(edgeLine[0]), Integer.parseInt(edgeLine[1]));
  106.         }
  107.         int nodeIndex=Integer.parseInt(br.readLine());
  108.         int pathLength=Integer.parseInt(br.readLine());
  109.         System.out.println(g.pathCount(nodeIndex, pathLength));
  110.         br.close();
  111.  
  112.     }
  113.  
  114. }
Add Comment
Please, Sign In to add comment