結果

問題 No.1805 Approaching Many Typhoon
ユーザー KnotsKnots
提出日時 2022-02-12 22:00:13
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
RE  
実行時間 -
コード長 2,465 bytes
コンパイル時間 2,140 ms
コンパイル使用メモリ 199,168 KB
最終ジャッジ日時 2025-01-27 22:48:04
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 28 RE * 7
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

const int INF = (1<<30)-1;
const int MOD = 1e9+7;
const ll LINF = (1ll<<62)-1;

#define REP(i,n) for(int i=0;i<(n);++i)
#define COUT(x) cout<<(x)<<"\n"
#define COUT16(x) cout << fixed << setprecision(16) << (x) << "\n";

//Union-Find
/*　
    連結成分に操作する際に利用する可能性が高い
    is_same(x,y):x,yが同じ集合にいるか
    unite(x,y):x,yを同じ集合にする
    treesize(x):xを含む集合の要素数
*/
struct UnionFind{
    vector<int> size,parents;
    UnionFind() {}
    UnionFind(int n){
        size.resize(n,0);
        parents.resize(n,0);
        for(int i=0;i<n;i++){
            makeTree(i);
        }
    }
    void makeTree(int x){
        parents[x] = x; //xの親はx
        size[x] = 1; //初期値の木のサイズは1
    }
    bool is_same(int x,int y){
        if(findroot(x)==findroot(y))return 1;///xとyの親が一緒なら1を返す
        else return 0;
    }
    bool unite(int x,int y){
        x = findroot(x);
        y = findroot(y);
        if(x==y)return 0;//xとyが同じならスルー
        //計算量逓減のために木の高さが低い方を高い方に接続
        if(size[x]>size[y]){
            parents[y] = x;
            size[x] += size[y];
        }
        else{
            parents[x] = y;
            size[y] += size[x];
        }
        return 1;//処理を終えた後,接続したことをreturn1で返す
    }
    int findroot(int x){
        if(x != parents[x]){
            parents[x] = findroot(parents[x]);
        }
        return parents[x];
    }
    int treesize(int x){
        return size[findroot(x)];
    }
};

int main(){
    int n,m,F,T,u,p;cin >> n >> m;
    vector<int> f(m+1),t(m+1),I;
    for(int i=0;i<m+1;i++){
        cin >> F >> T;
        f[i] = F;
        t[i] = T;
    }
    cin >> u;
    REP(i,u){
        cin >> p;
        I.push_back(p);
    }
    
    UnionFind uf(n);
    for(int i=1;i<m+1;i++){
        bool flag = 1;
        for(int j=0;j<u;j++){
            if(I[j]==t[i] || I[j]==f[i]){
                flag = 0;
            }
        }
        if(flag)uf.unite(f[i],t[i]);
    }
    if(uf.is_same(f[0],t[0])) cout << "Yes" << endl;
    else cout << "No" << endl;
}
0