Technologieaustausch

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

[Quelle der Frage]
https://www.acwing.com/problem/content/3590/

[Titel Beschreibung]
Bestimmen Sie anhand eines ungerichteten Graphen und aller darin enthaltenen Kanten, ob alle Eckpunkte dieses Graphen verbunden sind.

【Eingabeformat】
Die Eingabe enthält mehrere Datensätze.
Die erste Zeile jedes Datensatzes enthält zwei ganze Zahlen n und m, die die Anzahl der Punkte und Kanten des ungerichteten Graphen darstellen.
In den nächsten m Zeilen enthält jede Zeile zwei ganze Zahlen x, y, was darauf hinweist, dass Punkt x und Punkt y verbunden sind.
Die Punkte sind von 1 bis n nummeriert.
Möglicherweise auf dem BildzweischneidigUndSelbstschleife。

[Ausgabeformat]
Jeder Datensatz gibt eine Zeile und ein Ergebnis aus. Wenn alle Eckpunkte verbunden sind, geben Sie JA aus, andernfalls geben Sie NEIN aus.

【Datenreichweite】
Die Eingabe enthält bis zu 10 Datensätze.
1≤n≤1000,
1≤m≤5000,
1≤x,y≤n

【Eingabebeispiel】
4 3
1 2
2 3
3 2
3 2
1 2
2 3

【Ausgabebeispiel】
NEIN
JA

【Analyse von Algorithmen】
● Das „Und durchsuchen Sie die Sammlung„Details zur Code-Implementierung finden Sie unter:https://blog.csdn.net/hnjzsyjyj/article/details/126455868
● Das Prinzip der Verwendung von dfs zur Bestimmung des verbundenen Diagramms in dieser Frage liegt in „dfs muss in der Lage sein, alle Punkte des verbundenen Diagramms zu durchlaufen". Wenn ein Punkt nicht durchlaufen wird, bedeutet dies, dass er nicht verbunden ist.

[Algorithmuscode: dfs + verketteter Vorwärtsstern]
● DFS-Algorithmusvorlage:https://blog.csdn.net/hnjzsyjyj/article/details/118736059
● Einzelheiten zu Kettenvorwärtssternen finden Sie unter: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
*/

[Algorithmuscode: dfs + Adjazenzmatrix]
● DFS-Algorithmusvorlage:https://blog.csdn.net/hnjzsyjyj/article/details/118736059
● Adjazenzmatrix-Implementierung eines ungerichteten ungewichteten Graphen: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
*/

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