結果

問題 No.1390 Get together
ユーザー IKyoproIKyopro
提出日時 2021-02-13 15:41:56
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 74 ms / 2,000 ms
コード長 1,514 bytes
コンパイル時間 2,145 ms
コンパイル使用メモリ 198,276 KB
最終ジャッジ日時 2025-01-18 20:07:43
ジャッジサーバーID
(参考情報)
judge3 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 29
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template <class T> using vec = vector<T>;
template <class T> using vvec = vector<vec<T>>;
template<class T> bool chmin(T& a,T b){if(a>b) {a = b; return true;} return false;}
template<class T> bool chmax(T& a,T b){if(a<b) {a = b; return true;} return false;}
#define rep(i,n) for(int i=0;i<(n);i++)
#define drep(i,n) for(int i=(n)-1;i>=0;i--)
#define all(x) (x).begin(),(x).end()
#define debug(x) cerr << #x << " = " << (x) << endl;
class UnionFind{
private:
vec<int> p,s;
int cnt;
public:
UnionFind(){}
UnionFind(int N):cnt(N),s(N,1),p(N){
iota(p.begin(),p.end(),0);
}
int find(int x){
if(p[x]==x) return x;
else return p[x] = find(p[x]);
}
void unite(int x,int y){
x = find(x); y = find(y);
if(x==y) return;
if(s[x]>s[y]) swap(x,y);
p[x] = y;
s[y] += s[x];
cnt--;
}
int operator[](const int x){return find(x);}
bool is_same_set(int x,int y) {return find(x)==find(y);}
int size(int x) {return s[find(x)];}
int compnents_number(){return cnt;}
};
int main(){
cin.tie(0);
ios::sync_with_stdio(false);
int N,M;
cin >> N >> M;
vvec<int> C(N);
rep(i,N){
int b,c;
cin >> b >> c;
b--,c--;
C[c].push_back(b);
}
UnionFind uf(M);
for(auto& v:C){
for(auto& x:v){
uf.unite(v[0],x);
}
}
cout << M-uf.compnents_number() << "\n";
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0