fahad005

Untitled

Nov 30th, 2021
548
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. //
  4. #define ll long long
  5. #define ull unsigned long long
  6. #define mx 100010
  7. #define mod 1000000007
  8. #define inf INT_MAX
  9. #define pi acos(-1)
  10. #define endl '\n'
  11. #define pb push_back
  12. #define pll pair<ll, ll>
  13. #define Fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
  14. //
  15. vector<ll> adj[mx];
  16. vector<ll> visited(mx), TTL(mx);
  17.  
  18. void bfs(ll node, ll ttl) {
  19.     queue<ll> q;
  20.     q.push(node);
  21.  
  22.     TTL[node] = ttl;
  23.     while (!q.empty()) {
  24.         ll cNode = q.front();
  25.         q.pop();
  26.  
  27.         if (TTL[cNode] >= 0) {
  28.             if (TTL[cNode] == 0) {
  29.                 visited[cNode] = 1;
  30.                 continue;
  31.             }
  32.  
  33.             visited[cNode] = 1;
  34.             for (ll i = 0; i < adj[cNode].size(); i++) {
  35.                 if (!visited[adj[cNode][i]] && TTL[adj[cNode][i]] < TTL[cNode] - 1) {
  36.                     q.push(adj[cNode][i]);
  37.                     TTL[adj[cNode][i]] = TTL[cNode] - 1;
  38.                 }
  39.             }
  40.         }
  41.  
  42.     }
  43. }
  44. int main() {
  45.     ll tc = 1;
  46.  
  47.     while (1) {
  48.         ll nc;
  49.         cin >> nc;
  50.         if (nc == 0) break;
  51.  
  52.         adj->clear();
  53.  
  54.         set<ll> nodeCount;
  55.         for (ll i = 0; i < nc; i++) {
  56.             ll a, b;
  57.             cin >> a >> b;
  58.  
  59.             adj[a].pb(b);
  60.             adj[b].pb(a);
  61.  
  62.             nodeCount.insert(a);
  63.             nodeCount.insert(b);
  64.         }
  65.  
  66.         while (1) {
  67.             ll a, b;
  68.             cin >> a >> b;
  69.  
  70.             if (a == 0 && b == 0) break;
  71.  
  72.             for (auto it = nodeCount.begin(); it != nodeCount.end(); it++) {
  73.                 visited[*it] = 0;
  74.                 TTL[*it] = -1;
  75.             }
  76.  
  77.             bfs(a, b);
  78.  
  79.             ll count = 0;
  80.             for (auto it = nodeCount.begin(); it != nodeCount.end(); it++) {
  81.                 if (visited[*it] == 0) count++;
  82.             }
  83.  
  84.             cout << "Case " << tc++ << ": " << count <<
  85.                 " nodes not reachable from node " << a << " with TTL = " << b << "." << endl;
  86.         }
  87.     }
  88. }
RAW Paste Data