結果
問題 |
No.1805 Approaching Many Typhoon
|
ユーザー |
|
提出日時 | 2022-08-13 17:28:35 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 1,440 bytes |
コンパイル時間 | 2,171 ms |
コンパイル使用メモリ | 200,116 KB |
最終ジャッジ日時 | 2025-01-30 22:19:06 |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 35 |
ソースコード
typedef long long ll; typedef long double ld; #include <bits/stdc++.h> using namespace std; #define int long long struct UnionFind { vector<int> par; UnionFind() { } UnionFind(int n) : par(n, -1) { } void init(int n) { par.assign(n, -1); } int root(int x) { if (par[x] < 0) return x; else return par[x] = root(par[x]); } bool issame(int x, int y) { return root(x) == root(y); } bool merge(int x, int y) { x = root(x); y = root(y); if (x == y) return false; if (par[x] > par[y]) swap(x, y); // merge technique par[x] += par[y]; par[y] = x; return true; } int size(int x) { return -par[root(x)]; } }; signed main(){ ll n,m; std::cin >> n>>m; ll s,g; std::cin >> s>>g; s--;g--; vector<ll> a(m),b(m); for (int i = 0; i < m; i++) { std::cin >> a[i]>>b[i]; a[i]--; b[i]--; } ll u; std::cin >> u; vector<bool> dame(n); for (int i = 0; i < u; i++) { ll tmp; std::cin >> tmp; tmp--; dame[tmp]=true; } UnionFind uf(n); for (int i = 0; i < m; i++) { if(dame[a[i]]||dame[b[i]]){ }else{ uf.merge(a[i],b[i]); } } if(uf.issame(s,g)){ std::cout << "Yes" << std::endl; }else{ std::cout << "No" << std::endl; } }