CFR 794 D. Labelling Cities ( Ad hoc, Graph )

Problem - 794D - Codeforces

題意：
有 N 個城市，M 條路。如果存在，輸出一個方案，為每個城市 u 分配一個數字 X[ u ]，使得 abs( X[ u ] - X[ v ] ) ≤ 1 若且唯若 u, v 相鄰。

制約：
N, M ≤ 3e5

解法：
首先考慮這樣的一對城市 ( u, v )：它們的鄰接陣列，各自添上自己後是相同的。
給它們標一樣的號碼一定不會比較差，但是如果給他們不一樣的號碼 e.g. x, x + 1，此時令 a, b 都和 u 相鄰，因為 a, b 必須都被標號 x 或者 x + 1，所以會迫使 a, b 必需相鄰。反之，若 u, v 都是 x，a, b 就相對自由了，沒有這個限制。
把這些「相同」的點集合縮成一個點後，可以發現有幾個條件必須滿足，才能有想要輸出的圖。
一、不能存在環：會存在 abs( X[ u ] - X[ v ] ) ≤ 1，( u, v ) 卻不相鄰
二、一個點的最大度數為 2：由條件一可知顯然
那麼，這張圖肯定是條純樸的路徑，找一個頭掃到尾就可以了。

複雜度：
O( N lg N )

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

const int MAXN = int( 3e5 );
const int MAXM = int( 3e5 );

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

set< int > gadj[ MAXN ]; // adjacency relations between groups

int gans[ MAXN ];
void dfs( int u, int fa, int cnt ) {
  gans[ u ] = cnt;
  for( int v: gadj[ u ] ) {
    if( v == fa ) continue;
    dfs( v, u, cnt + 1 );
  }
}

signed main() {
  ios::sync_with_stdio( 0 );
  cin >> N >> M;
  for( int i = 0; i < M; ++i ) {
    int u, v;
    cin >> u >> v;
    G[ u - 1 ].emplace_back( v - 1 );
    G[ v - 1 ].emplace_back( u - 1 );
  }
  for( int i = 0; i < N; ++i ) {
    G[ i ].emplace_back( i );
    sort( G[ i ].begin(), G[ i ].end() );
    tmp[ i ] = G[ i ];
  }
  sort( tmp, tmp + N );
  int usize = unique( tmp, tmp + N ) - tmp;
  if( usize == 1 ) {
    cout << "YES" << endl;
    for( int i = 0; i < N; ++i ) {
      cout << 1 << " \n"[ i + 1 == N ];
    }
    exit( 0 );
  }
  for( int i = 0; i < N; ++i ) {
    id[ i ] = lower_bound( tmp, tmp + usize, G[ i ] ) - tmp;
  }
  for( int i = 0; i < N; ++i ) {
    for( int j = 0; j < G[ i ].size(); ++j ) {
      if( id[ i ] == id[ G[ i ][ j ] ] ) continue;
      gadj[ id[ i ] ].emplace( id[ G[ i ][ j ] ] );
      gadj[ id[ G[ i ][ j ] ] ].emplace( id[ i ] );
    }
  }
  int deg1 = 0, st;
  for( int i = 0; i < usize; ++i ) {
    if( gadj[ i ].size() > 2 ) {
      cout << "NO" << endl;
      exit( 0 );
    }
    if( gadj[ i ].size() == 1 ) {
      ++deg1;
      st = i;
    }
  }
  if( not ( 1 <= deg1 and deg1 <= 2 ) ) {
    cout << "NO" << endl;
    exit( 0 );
  }
  dfs( st, -1, 1 );
  cout << "YES" << endl;
  for( int i = 0; i < N; ++i ) {
    cout << gans[ id[ i ] ] << " \n"[ i + 1 == N ];
  }
  return 0;
}