Advertisement
Hasan1026

A Node too far

Jan 22nd, 2022
828
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2. *@Author: Kabid Hasan
  3. *@Date: Sunday 2021-Apr-25
  4. *@Time: 16:35:52
  5. */
  6. #include <bits/stdc++.h>
  7.  
  8. using namespace std;
  9.  
  10. typedef long long ll;
  11. typedef long double ld;
  12. typedef pair<int, int> p32;
  13. typedef pair<ll, ll> p64;
  14. typedef pair<double, double> pdd;
  15. typedef vector<ll> v64;
  16. typedef vector<int> v32;
  17. typedef vector<vector<int> > vv32;
  18. typedef vector<vector<ll> > vv64;
  19. typedef vector<vector<p64> > vvp64;
  20. typedef vector<p64> vp64;
  21. typedef vector<p32> vp32;
  22. ll MOD = 998244353;
  23. double eps = 1e-12;
  24. #define forn(i,e) for(ll i = 0; i < e; i++)
  25. #define forsn(i,s,e) for(ll i = s; i < e; i++)
  26. #define rforn(i,s) for(ll i = s; i >= 0; i--)
  27. #define rforsn(i,s,e) for(ll i = s; i >= e; i--)
  28. #define ln "\n"
  29. #define dbg(x) cout<<#x<<" = "<<x<<ln
  30. #define mp make_pair
  31. #define pb push_back
  32. #define fi first
  33. #define se second
  34. #define INF 2e18
  35. #define fast_cin() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
  36. #define all(x) (x).begin(), (x).end()
  37. #define sz(x) ((ll)(x).size())
  38.  
  39. int bfs(int n, vector<int>  ad[], int st, int ttl) {
  40.     vector<int> vis(10000, -1);
  41.     queue<int> q;
  42.     q.push(st);
  43.     vis[st] = 0;
  44.     int c = 1;
  45.     while (q.size()) {
  46.         int fr = q.front();
  47.         if (vis[fr] == ttl) break;
  48.         q.pop();
  49.         for (auto nd : ad[fr]) {
  50.             if (vis[nd] == -1) {
  51.                 vis[nd] = vis[fr] + 1;
  52.                 q.push(nd);
  53.                
  54.                 c++;
  55.             }
  56.         }
  57.        
  58.  
  59.     }
  60.    
  61.     return n - c;
  62. }
  63.  
  64. void solve()
  65. {   int cs=0;
  66.     int nc;
  67.     while (cin >> nc and nc) {
  68.         set<int> st;
  69.         vector<int> ad[10000];
  70.         int n = nc;
  71.         while (nc--) {
  72.            
  73.             int a, b;
  74.             cin >> a >> b;
  75.             ad[a].pb(b);
  76.             ad[b].pb(a);
  77.             st.insert(a); st.insert(b);
  78.  
  79.         }
  80.  
  81.         int a,b;
  82.         while (cin >> a >> b and a) {
  83.            
  84.             cout << "Case " << ++cs << ": "<< bfs(st.size(), ad, a, b) <<" nodes not reachable from node "<<a<<" with TTL = "<<b<< endl;
  85.         }
  86.  
  87.  
  88.     }
  89.  
  90.  
  91. }
  92.  
  93.  
  94.  
  95. int main()
  96. {
  97.     fast_cin();
  98.     ll t = 1;
  99.     //cin >> t;
  100.     for ( int it = 1; it <= t; it++) {
  101.         //cout << "Case " << it << ": ";
  102.         solve();
  103.     }
  104.     return 0;
  105. }
  106.  
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement