2012年11月27日

UVa 336 - A Node Too Far


#include <cstdio>
#include <map>
#include <vector>
#include <queue>
#include <set>
#define MP make_pair
using namespace std;
typedef pair<int, int> P;

int main() {
  int i, n, c = 1;
  while (scanf("%d", &n) && n) {
    map<int, vector<int> > road;
    set<int> number;
    while (n--) {
      int a, b;
      scanf("%d%d", &a, &b);
      number.insert(a);
      number.insert(b);
      road[a].push_back(b);
      road[b].push_back(a);
    }
    int s, l;
    while (scanf("%d%d", &s, &l) && s || l) {
      queue<P> q;
      set<int> visit;
      visit.insert(s);
      q.push(MP(s, 0));
      int ans = 0;
      while (!q.empty()) {
        int now = q.front().first, dis = q.front().second;
        q.pop();
        if (dis <= l) ans++;
        else break;
        for (i = 0; i < road[now].size(); i++) {
          int next = road[now][i];
          if (!visit.count(next)) {
            q.push(MP(next, dis + 1));
            visit.insert(next);
          }
        }
      }
      printf("Case %d: %d nodes not reachable from node %d with TTL = %d.\n", c++, number.size() - ans, s, l);
    }
  }
  return 0;
}

沒有留言:

張貼留言