SHARE
TWEET

Untitled

Srivatsa11 Oct 9th, 2018 66 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdio.h>
  2. #include <stdbool.h>
  3. #define V 101
  4.  
  5. bool isLeaf (int graph[V][V], int u, int n) {
  6.     for (int v = u + 1; v <= n; v++) {
  7.         if (graph[u][v])
  8.             return (false);
  9.     }
  10.     return (true);
  11. }
  12.  
  13. void DFS (int graph[V][V], bool hasCat[V], int u, int n, int m, int *c, int *r) {
  14.    
  15.     if (hasCat[u]) {
  16.         *c = *c + 1;
  17.         if (*c > m) {
  18.             *c = *c  - 1;
  19.             return;
  20.         }
  21.     }
  22.    
  23.     if (isLeaf(graph, u, n)) {
  24.         *r = *r + 1;
  25.         return;
  26.     }
  27.    
  28.     for (int v = u + 1; v <= n; v++) {
  29.         if (graph[u][v]) {
  30.             DFS(graph, hasCat, v, n, m, c, r);
  31.         }
  32.     }
  33. }
  34.  
  35. int main () {
  36.     int graph[V][V];
  37.     int n;
  38.     int m;
  39.     int u;
  40.     int v;
  41.     bool hasCat[V];
  42.     int cats;
  43.     int restaurants;
  44.     int temp;
  45.    
  46.     for (int i = 0; i < V; i++) {
  47.         for (int j = 0; j < V; j++) {
  48.             graph[i][j] = 0;
  49.         }
  50.         hasCat[i] = false;
  51.     }
  52.    
  53.     scanf("%d %d", &n, &m);
  54.     for (int i = 1; i <= n; i++) {
  55.         scanf("%d", &temp);
  56.         hasCat[i] = (bool)temp;
  57.     }
  58.     for (int i = 1; i < n; i++) {
  59.         scanf("%d %d", &u, &v);
  60.         graph[u][v] = 1;
  61.     }
  62.    
  63.     cats = 0;
  64.     restaurants = 0;
  65.     DFS(graph, hasCat, 1, n, m, &cats, &restaurants);
  66.    
  67.     printf("%d\n", restaurants);
  68.     return (0);
  69. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top