技術共有

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

【質問元】
https://www.acwing.com/problem/content/3590/

[タイトル説明]
無向グラフとその中のすべてのエッジが与えられた場合、このグラフのすべての頂点が接続されているかどうかを判断します。

【入力形式】
入力には複数のデータセットが含まれています。
データの各セットの最初の行には、無向グラフの点とエッジの数を表す 2 つの整数 n と m が含まれています。
次の m 行には、各行に 2 つの整数 x、y が含まれており、点 x と点 y が接続されていることを示します。
ポイントには 1 から n までの番号が付けられます。
写真にあるかもしれない両刃そしてセルフループ。

[出力フォーマット]
各データセットは 1 つの行と 1 つの結果を出力します。すべての頂点が接続されている場合は YES を出力し、そうでない場合は NO を出力します。

【データ範囲】
入力には最大 10 セットのデータが含まれます。
1≤n≤1000、
1≤m≤5000、
1≤x,y≤n

【入力サンプル】
4 3
1 2
2 3
3 2
3 2
1 2
2 3

【出力サンプル】
いいえ
はい

【アルゴリズムの解析】
●「」そしてコレクションを検索してください「コード実装の詳細については、以下を参照してください。https://blog.csdn.net/hnjzsyjyj/article/details/126455868
● この質問で dfs を使用して接続グラフを決定する原理は、「」にあります。dfs は接続されたグラフのすべての点を走査できなければなりません"。ポイントを通過しない場合、それは接続されていないことを意味します。

[アルゴリズムコード: dfs+チェインフォワードスター]
● dfs アルゴリズム テンプレート:https://blog.csdn.net/hnjzsyjyj/article/details/118736059
●チェーンフォワードスターの詳細については、以下をご覧ください。https://blog.csdn.net/hnjzsyjyj/article/details/139369904

#include <bits/stdc++.h>
using namespace std;
 
const int N=1e3+5;
const int M=5e3+5;
int e[M<<1],ne[M<<1],h[N],idx;
bool st[N];
int n,m;
 
void add(int a,int b) {
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
 
void dfs(int u) {
    st[u]=1;
    for(int i=h[u]; i!=-1; i=ne[i]) {
        int j=e[i];
        if(!st[j]) dfs(j);
    }
}
 
int main() {
    while(cin>>n>>m) {
        memset(st,false,sizeof st);
        memset(h,-1,sizeof h);
        idx=0;
        while(m--) {
            int a,b;
            cin>>a>>b;
            add(a,b),add(b,a);
        }
 
        dfs(1);
 
        bool flag=true;
        for(int i=1; i<=n; i++)
            if(!st[i]) {
                flag=false;
                break;
            }
 
        if(flag) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
 
    return 0;
}
 
 
/*
in:
4 3
1 2
2 3
3 2
3 2
1 2
2 3
out:
NO
YES
*/

［アルゴリズムコード：dfs+隣接行列］
● dfs アルゴリズム テンプレート:https://blog.csdn.net/hnjzsyjyj/article/details/118736059
● 無向無重みグラフの隣接行列の実装:https://blog.csdn.net/hnjzsyjyj/article/details/116245897

#include <bits/stdc++.h>
using namespace std;
 
const int N=1010;
int g[N][N];
bool st[N];
int n,m;
 
void dfs(int u) {
    st[u]=true;
    for(int i=1; i<=n; i++)
        if(!st[i] && g[u][i]!=0) dfs(i);
}
 
int main() {
    while(cin>>n>>m) {
        memset(g,0,sizeof g);
        memset(st,false,sizeof st);
        int x,y;
        while(m--) {
            cin>>x>>y;
            g[x][y]=g[y][x]=1;
        }
        dfs(1);
        int i;
        for(i=1; i<=n; i++) {
            if(!st[i]) break;
        }
        if(i<=n) cout<<"NO"<<endl;
        else cout<<"YES"<<endl;
    }
    return 0;
}
 
/*
in:
4 3
1 2
2 3
3 2
3 2
1 2
2 3
out:
NO
YES
*/

【参考文献】
https://www.acwing.com/solution/content/124095/
https://blog.csdn.net/hnjzsyjyj/article/details/118736059
https://blog.csdn.net/hnjzsyjyj/article/details/139369904