fahad005

Untitled

Nov 30th, 2021
607
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> visited(mx), TTL(mx);
  16.  
  17. void bfs(ll node, ll ttl, vector<ll> adj[]) {
  18.     queue<ll> q;
  19.     q.push(node);
  20.  
  21.     TTL[node] = ttl;
  22.     visited[node] = 1;
  23.     while (!q.empty()) {
  24.         ll cNode = q.front();
  25.         q.pop();
  26.  
  27.         for (ll i = 0; i < adj[cNode].size(); i++) {
  28.             if (!visited[adj[cNode][i]] && TTL[cNode] > 0) {
  29.                 q.push(adj[cNode][i]);
  30.                 visited[adj[cNode][i]] = 1;
  31.                 TTL[adj[cNode][i]] = TTL[cNode] - 1;
  32.             }
  33.         }
  34.  
  35.     }
  36. }
  37. int main() {
  38.     ll tc = 1;
  39.  
  40.     while (1) {
  41.         ll nc;
  42.         cin >> nc;
  43.         if (nc == 0) break;
  44.  
  45.         set<ll> nodeCount;
  46.         vector<ll> adj[mx];
  47.  
  48.         for (ll i = 0; i < nc; i++) {
  49.             ll a, b;
  50.             cin >> a >> b;
  51.  
  52.             adj[a].pb(b);
  53.             adj[b].pb(a);
  54.  
  55.             nodeCount.insert(a);
  56.             nodeCount.insert(b);
  57.         }
  58.  
  59.         while (1) {
  60.             ll a, b;
  61.             cin >> a >> b;
  62.  
  63.             if (a == 0 && b == 0) break;
  64.  
  65.             for (auto it = nodeCount.begin(); it != nodeCount.end(); it++) {
  66.                 visited[*it] = 0;
  67.                 TTL[*it] = -1;
  68.             }
  69.  
  70.             auto it = nodeCount.find(a);
  71.  
  72.             if (it != nodeCount.end()) {
  73.                 bfs(a, b, adj);
  74.  
  75.                 ll count = 0;
  76.                 for (auto it = nodeCount.begin(); it != nodeCount.end(); it++) {
  77.                     if (visited[*it] == 0) count++;
  78.                 }
  79.  
  80.                 cout << "Case " << tc++ << ": " << count << " nodes not reachable from node " << a << " with TTL = " << b << "." << endl;
  81.             }
  82.             else {
  83.                 cout << "Case " << tc++ << ": " << nodeCount.size() << " nodes not reachable from node " << a << " with TTL = " << b << "." << endl;
  84.             }
  85.         }
  86.     }
  87. }
RAW Paste Data