結果
問題 | No.1390 Get together |
ユーザー |
|
提出日時 | 2021-02-12 21:49:23 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 226 ms / 2,000 ms |
コード長 | 2,146 bytes |
コンパイル時間 | 1,305 ms |
コンパイル使用メモリ | 103,528 KB |
最終ジャッジ日時 | 2025-01-18 18:20:48 |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 29 |
ソースコード
#include <iostream>#include <algorithm>#include <vector>#include <string>#include <utility>#include <set>#include <map>#include <cmath>#include <queue>#include <cstdio>#include <limits>#define rep(i,n) for(int i = 0; i < n; ++i)#define rep1(i,n) for(int i = 1; i <= n; ++i)using namespace std;template<class T>bool chmax(T &a, const T &b) { if(a < b){ a = b; return 1; } return 0; }template<class T>bool chmin(T &a, const T &b) { if(a > b){ a = b; return 1; } return 0; }template<class T> inline int sz(T &a) { return a.size(); }using ll = long long; using ld = long double;using pi = pair<int,int>; using pl = pair<ll,ll>;using vi = vector<int>; using vvi = vector<vi>;using vl = vector<ll>; using vvl = vector<vl>;const int inf = numeric_limits<int>::max();const ll infll = numeric_limits<ll>::max();struct UFT{vector<int> par;//親vector<int> rank;//木の深さvector<int> size;//木の大きさint n;UFT(int _n){n = _n;par.resize(n);rank.assign(n,0);size.assign(n,0);rep(i,n){par[i] = i;}}//xの根を返すint find(int x){if(par[x] == x) return x;else return par[x] = find(par[x]);}//x,yを併合void unite(int x,int y){x = find(x);y = find(y);if(x == y) return;if(rank[x] < rank[y]){par[x] = y;size[y] += size[x];}else{par[y] = x;size[x] += size[y];if(rank[x] == rank[y]) rank[x]++;}}//x,yが同じグループにいるかどうかを返すbool same(int x,int y){return find(x) == find(y);}//xの属する木のサイズを探すint usize(int x){return size[find(x)];}};int main(){int n,m; cin >> n >> m;vvi a(m+1);rep(i,n) {int b,c; cin >> b >> c;a[b].push_back(c);}UFT uf(n+1);rep1(i,m) {if(sz(a[i]) >= 2) {rep1(j,sz(a[i])-1) uf.unite(a[i][0], a[i][j]);}}vi tab(n+1, 0);int res = 0;rep1(i,m) {if(sz(a[i]) == 0) continue;int x = uf.find(a[i][0]);if(tab[x] == 0) tab[x]++;else res++;}cout << res << "\n";return 0;}