BOJ 15752 - Hoofball

BOJ 15752 - Hoofball

항상 outdegree=1 인 모든 정점들의 그래프이다.

in degree=0인 곳을 모두 탐색해준뒤, 이만큼 정답에 더해준다.

그리고 아직 방문되지 않은 곳들은 튀어나와있는 정점 없는 완벽히 싸이클을 이루는 곳이므로 그것들의 개수도 정답에 더해준다.

void solve() {  
   int n;  
   cin >> n;  
   vi a(n + 1, -1);  
   fv1(a);  
   sort(all(a));  
   debug(a);  
   int ans = 0;  
   auto to_right = [&](int i) {  
      if (i == 1) return true;  
      return i != n && a[i + 1] - a[i] < a[i] - a[i - 1];  
   };  
   vi in(n + 2);  
   for (int i = 1; i <= n; i++) {  
      if (to_right(i)) in[i + 1]++;  
      else in[i - 1]++;  
   }  
   debug(in);  
   vi vis(n + 1);  
   for (int i = 1; i <= n; i++) debug(i, to_right(i));  
   for (int i = 1; i <= n; i++) {  
      if (in[i] == 0) {  
         assert(vis[i] == 0);  
         vis[i] = 1;  
         ans++;  
         queue<int> q;  
         q.push(i);  
         while (sz(q)) {  
            int cur = q.front();  
            q.pop();  
            int nxt;  
            if (to_right(cur)) nxt = cur + 1;  
            else nxt = cur - 1;  
            if (!vis[nxt]) {  
               vis[nxt] = 1;  
               q.push(nxt);  
            }  
         }  
      }  
   }  
   for (int i = 1; i <= n; i++) {  
      if (!vis[i]) {  
         ans++;  
         vis[i] = 1;  
         queue<int> q;  
         q.push(i);  
         while (sz(q)) {  
            int cur = q.front();  
            q.pop();  
            int nxt;  
            if (to_right(cur)) nxt = cur + 1;  
            else nxt = cur - 1;  
            if (!vis[nxt]) {  
               vis[nxt] = 1;  
               q.push(nxt);  
            }  
         }  
      }  
   }  
   cout << ans;  
}