ARC 065 D - 連結 ( Ad hoc )

D: 連結 / Connectivity - AtCoder Regular Contest 065 | AtCoder

題意：
給相同節點數的兩個圖，對於每個點，求有多少點和它在兩個圖上都屬於相同的連通分量。

資料規模：
節點數 2≦N≦2e5
兩個圖分別邊數 1≦K,L≦1e5
保證同一個圖不存在重邊
時限 2000 ms
記憶體 256 MB

解法：
先將每個節點做連通分量編號，令 i 點的編號在圖一為 cc1_id[ i ]，在圖二為 cc2_id[ i ]，則 ( i, j ) 對彼此有貢獻若且唯若 cc1_id[ i ] == cc1_id[ j ] and cc2_id[ i ] == cc2_id[ j ]。這部分用 map 處理一下就行了。

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

int N, K, L;
vi P, Q;
vi R, S;

void init(){
  cin >> N >> K >> L;
  P = Q = vi( K );
  for( int i = 0; i < K; ++i )
    cin >> P[ i ] >> Q[ i ], --P[ i ], --Q[ i ];
  R = S = vi( L );
  for( int i = 0; i < L; ++i )
    cin >> R[ i ] >> S[ i ], --R[ i ], --S[ i ];
}

vvi G1, G2;
vi cc1_id, cc2_id;

void dfs( const vvi &g, int u, vi &cc_id ){
  for( int v : g[ u ] )
    if( cc_id[ v ] == -1 )
      cc_id[ v ] = cc_id[ u ],
      dfs( g, v, cc_id );
}

void preprocess(){
  G1 = vvi( N );
  for( int i = 0; i < K; ++i )
    G1[ P[ i ] ].emplace_back( Q[ i ] ),
    G1[ Q[ i ] ].emplace_back( P[ i ] );
  G2 = vvi( N );
  for( int i = 0; i < L; ++i )
    G2[ R[ i ] ].emplace_back( S[ i ] ),
    G2[ S[ i ] ].emplace_back( R[ i ] );
  cc1_id = vi( N, -1 );
  int cc_cnt = -1;
  for( int i = 0; i < N; ++i )
    if( cc1_id[ i ] == -1 )
      cc1_id[ i ] = ++cc_cnt,
      dfs( G1, i, cc1_id );
  cc2_id = vi( N, -1 );
  cc_cnt = -1;
  for( int i = 0; i < N; ++i )
    if( cc2_id[ i ] == -1 )
      cc2_id[ i ] = ++cc_cnt,
      dfs( G2, i, cc2_id );
}

void solve(){
  map< pii, int > cnt;
  map< pii, vi > node;
  for( int i = 0; i < N; ++i )
    ++cnt[ make_pair( cc1_id[ i ], cc2_id[ i ] ) ],
    node[ make_pair( cc1_id[ i ], cc2_id[ i ] ) ].emplace_back( i );
  vi ans( N );
  for( auto it = cnt.begin(); it != cnt.end(); ++it )
    for( auto v : node[ it->first ] )
      ans[ v ] = it->second;
  for( int i = 0; i < N; ++i )
    cout << ans[ i ] << " \n"[ i + 1 == N ];
}