Submission #421760

---

Source Code Expand

#include <iostream>
#include <cstdlib>

using namespace std;

enum Query {
  CONCAT = 0,
  JUDGE = 1
};

const static int VN_MAX = 100010;
int v_parent[ VN_MAX ];
int v_rank[ VN_MAX ];

void uf_init( int vn ) {
  for( int i = 0; i < vn; i++ ) {
    v_parent[ i ] = i;
    v_rank[ i ] = 0;
  }
}

int uf_root( int vid ) {
  if( v_parent[ vid ] == vid ) {
    return vid;
  }
  return v_parent[ vid ] = uf_root( v_parent[ vid ] ); // !
}

bool uf_issamegroup( int vid1, int vid2 ) {
  return uf_root( vid1 ) == uf_root( vid2 );
}

void uf_unite( int vid1, int vid2 ) {
  int r1 = uf_root( vid1 );
  int r2 = uf_root( vid2 );
  if( r1 == r2 ) {
    return;
  }

  if( v_rank[ r1 ] >= v_rank[ r2 ] ) {
    v_parent[ r2 ] = r1;
    if( v_rank[ r1 ] == v_rank[ r2 ] ) {
      v_rank[ r1 ]++;
    }
  } else {
    v_parent[ r1 ] = r2;
  }
}

int main() {
  int vn, qn;
  cin >> vn >> qn;
  uf_init( vn );
  for( int qi = 0; qi < qn; qi++ ) {
    int qtype, v1, v2;
    cin >> qtype >> v1 >> v2;
    if( qtype == CONCAT ) {
      uf_unite( v1, v2 );
    } else if( qtype == JUDGE ) {
      cout << ( uf_issamegroup( v1, v2 ) ? "Yes" : "No" ) << endl;
    } else {
      // error
    }
  }

  return EXIT_SUCCESS;
}

Submission Info

Judge Result