BOJ 1375 - 나이

간만에 알고리즘 문제를 포스팅한다.

BOJ 1375 - 나이

적당히 수가 크고 $Q \le 20$ 이므로 브루트포스 + BFS로 충분히 풀린다.

문자열에 대해 전처리만 잘 빠르게 해주면 된다. 나는 먼저 문자열을 정수로 모두 hash 해두는 식으로 해결했다.

시간복잡도는 $O(QE)$ 정도이다.

void solve() {
   int n, m;
   cin >> n >> m;
   vvi edges(n);
   unordered_map<string, int> name_idx;
   for (int i = 0; i < m; i++) {
      string u, v;
      cin >> u >> v;
      if (!hass(name_idx, u)) name_idx[u] = sz(name_idx);
      if (!hass(name_idx, v)) name_idx[v] = sz(name_idx);
      edges[name_idx[u]].pb(name_idx[v]);
   }

   int q, cycle = 0;
   cin >> q;
   while (q--) {
      string _u, _v;
      cin >> _u >> _v;

      //assert(_u != _v);
      if (_u == _v) {
         cout << "gg ";
         continue;
      }
      if (!hass(name_idx, _u) || !hass(name_idx, _v)) {
         cout << "gg ";
         continue;
      }

      int u = name_idx[_u];
      int v = name_idx[_v];
      int f = 0;
      for (int it = 0; it < 2; it++) {
         queue<int> q;
         bitset<1000000> vis;
         q.push(u);
         vis[u] = 1;
         while (sz(q)) {
            int cur = q.front();
            q.pop();
            for (int to: edges[cur]) {
               if (!vis[to]) vis[to] = 1, q.push(to);
            }
         }

         if (vis[v]) {
            if (it == 0) cout << _u << ' ';
            else cout << _v << ' ';
            f = 1;
            break;
         }

         swap(u, v);
      }
      if (!f) cout << "gg ";
   }
}