CodeTON Round 4 (Div. 1 + Div. 2, Rated, Prizes!) - E. Monsters (2100)

E. Monsters

내 풀이

Multi-source BFS + DSU + Small To Large로 풀었다.

$a_i=0$ 인 것들을 모두 큐에 넣고 만나게 되는 것들은 DSU에서 merge 해준다.

이 과정에서 현재 $u$에 있고 인접한 노드 $v$에 대해 $a_v$ 가 아직 현재 집합의 크기보다 커서 못가는 경우, $u$의 집합에 다음과 같이 pair 를 추가한다.

($a_v$, $v$)

이 집합도 DSU에서 각 노드마다 관리하며 Small to Large로 MLE나 TLE를 피한다.

이제 어떤 노드 $c$에 방문했을 때 pending 된 것 들 중 방문되지 않고 현재 집합의 크기보다 $a_i$ 가 이하인 것이 있다면 방문해준다.

집합을 다룰땐 iterator를 쓰는 것보다 while 문으로 뭔가 작업을 해주는게 동시 변경 에러를 피하는 안전한 구현법이 되는 것 같다. Small to Large문제를 몇개 풀어보긴 해야겠다.

struct DSU {
   vector<int> p;
   vector<set<pi>> pending;
   DSU(int n) : p(n, -1), pending(n) {}
   int gp(int n) {
      if (p[n] < 0) return n;
      return p[n] = gp(p[n]);
   }
   void merge(int a, int b) {
      a = gp(a), b = gp(b);
      if (a == b) return;
 
      // a를 b에 merge,
      if (sz(pending[a]) > sz(pending[b])) swap(a, b);
 
      p[b] += p[a];
      p[a] = b;
 
      for (auto &[pending_cnt, node]: pending[a]) {
         pending[b].insert({pending_cnt, node});
      }
   }
   bool is_merged(int a, int b) { return gp(a) == gp(b); }
   int size(int n) { return -p[gp(n)]; }
};
void solve() {
   int n, m;
   cin >> n >> m;
   vvi edges(n);
   vi a(n);
   fv(a);
   for (int i = 0, u, v; i < m; i++) cin >> u >> v, u--, v--, edges[u].pb(v), edges[v].pb(u);
 
   vi slist;
   queue<int> q;
   DSU dsu(n);
   vi vis(n);
   for (int i = 0; i < n; i++) {
      if (a[i] == 0) {
         q.push(i);
         vis[i] = 1;
      }
   }
   while (sz(q)) {
      int cur = q.front();
      q.pop();
      for (int to: edges[cur]) {
         if (vis[to]) {
            if (!dsu.is_merged(cur, to)) {
               dsu.merge(to, cur);
            }
         } else {
            if (a[to] <= dsu.size(cur)) {
               vis[to] = 1;
               q.push(to);
               dsu.merge(to, cur);
            } else {
               cur = dsu.gp(cur);
               dsu.pending[cur].insert({a[to], to});
            }
         }
      }
 
      cur = dsu.gp(cur);
      while (sz(dsu.pending[cur])) {
         auto it = dsu.pending[cur].begin();
         if (it->fi <= dsu.size(cur)) {
            int nxt = it->se;
            if (vis[nxt]) {
               if (!dsu.is_merged(cur, nxt)) {
                  dsu.merge(nxt, cur);
               }
            } else {
               dsu.merge(nxt, cur);
               q.push(nxt);
               vis[nxt] = 1;
            }
            dsu.pending[cur].erase(it);
         } else break;
      }
   }
   if (cntt(vis, 1) == n && dsu.size(0) == n) cout << "yes\n";
   else cout << "no\n";
}
 

에디토리얼 풀이

$S(u)$를 $u$에서 시작해 도달할 수 있는 정점 집합이라고 하자.

정점 집합 $T$에 대해 $E(T)$를 $T$들 정점의 인접 리스트 정점 목록이라고 하자.

어떤 고정된 정점 $u$로부터 문제를 해결하기 위해 $S(u)$와 $E(S(u))$ 를 집합으로 관리한다.

처음에 $S(u)=u$ 이다. $v \in E(S(u))$ 인 $v$ 들 중 가장 작은 $a_v$ 를 가진 $v$ 를 살핀다.

만약 $a_v \le \vert S(u) \vert$ 라면 $v$를 $S(u)$에 추가할 수 있다. 같이 $E(S(u))$ 도 업데이트한다.

결국 우리의 목적은 어떤 $u$가 $\vert S(u) \vert=n$ 이 되게 하는 것이다.

Lemma - if $v \in S(u)$, then $S(v) \subseteq S(u)$

그렇지 않다면 위의 과정에서 $x \not\in S(u)$이고 인 $x$를 $S(v)$에 추가한다 하자.

이 때, $\vert S(v) \vert < \vert S(u) \vert$ 여야 한다.(이건 $S(u)$에 없는 정점을 추가한 처음 순간이기 때문에, 만약 $S(u)=S(v)$ 였다면 $x$는 무조건 $S(u)$에도 추가되므로 이 경우는 고려하지 않는다)

그럼 $x \in E(S(u))$ 여야 하고 $a_x > \vert S(u) \vert \ge \vert S(v) \vert$ 이기 때문에 모순이다.

따라서 우린 $x$를 $S(v)$에 추가할 수 없다.

---

따라서 $\vert S(u) \vert < n$ 이라면 $v \in S(u)$ 인 모든 $v$에 대해서 탐색할 필요가 없기 때문에 모든 $i$ 에 대해 방문되지 않은 상태일 때만 검사해줄 수 있다.

각 정점 $v$에 대해 만약 $v \in S(u)$라면 어떤 $u'$에서 알고리즘을 시작할 때 $v$는 $S(u')$에 또 포함될 수 있다.

그럼 $\vert S(u') \vert > 2\vert S(u) \vert$가 된다.

$u$ 에서 시작했을 때 방문되지 못한 정점 $x$가 $u'$ 에서 시작되었을 때 방문되었다면 $x$를 방문하기 전까지 $\vert S(u') \vert$가 $\vert S(u) \vert$보다 컸다는 것이므로 최소 두배보다 커야한다.

한번 방문될 때 집합의 크기가 두배 커지므로 한 정점은 최대 $O(\log n)$번 방문되고(실제로는 더 적게 방문될 것)

set 의 시간복잡도를 고려해 $O(n \log ^2n)$에 문제가 해결된다.