CFR 781 C. Underground Lab ( Ad hoc, Time Stamp, DFS )

Problem - C - Codeforces

題意：
給一個圖，要求放 K 個機器人並給出每個機器人的路徑，路徑長至多為 ceil( 2 * N / K )，使得所有節點都被至少一個機器人拜訪過。

資料規模：
N, M ≤ 2e5

解法：
首先把圖轉換成任意一個生成樹。接著進行類似時間戳記的 DFS，把樹變成一個長度為 2 * N 的路徑。接著顯然就能直接分配路徑。

時間 / 空間複雜度：
O( N + M ) / O( N )

#include <bits/stdc++.h>
using namespace std;

const int MAXN = ( int ) 2e5;

int N, M, K;
vector< int > G[ MAXN ];

struct dsu{
  vector< int > fa;
  dsu( int size ){
    fa = vector< int >( size );
    for( int i = 0; i < size; ++i ){
      fa[ i ] = i;
    }
  }
  int find( int x ){
    return fa[ x ] == x ? x : fa[ x ] = find( fa[ x ] );
  }
  bool unite( int x, int y ){
    int a = find( x );
    int b = find( y );
    if( a == b ) return 0;
    fa[ a ] = b;
    return 1;
  }
};

void dfs( int u, int fa, vector< int > &seq ){
  seq.emplace_back( u );
  for( int v : G[ u ] ){
    if( v == fa ) continue;
    dfs( v, u, seq );
    seq.emplace_back( u );
  }
}

signed main(){
  ios::sync_with_stdio( 0 );
  {
    cin >> N >> M >> K;
    dsu *uf = new dsu( N );
    for( int i = 0; i < M; ++i ){
      int x, y;
      cin >> x >> y;
      --x, --y;
      if( uf->unite( x, y ) ){
        G[ x ].emplace_back( y );
        G[ y ].emplace_back( x );
      }
    }
  }
  {
    vector< int > seq;
    dfs( 0, -1, seq );
    vector< vector< int > > ans( K );
    for( int i = 0; i < seq.size(); ){
      static int id = 0;
      for( int j = 0; j < ( 2 * N + K - 1 ) / K and i < seq.size(); ++j, ++i ){
        ans[ id ].emplace_back( seq[ i ] + 1 );
      }
      ++id;
    }
    for( int i = 0; i < K; ++i ){
      if( ans[ i ].empty() ){
        cout << "1 1\n";
      } else{
        cout << ans[ i ].size() << " ";
        for( int j = 0; j < ans[ i ].size(); ++j ){
          cout << ans[ i ][ j ] << " \n"[ j + 1 == ans[ i ].size() ];
        }
      }
    }
  }
  return 0;
}