Κοινή χρήση τεχνολογίας

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

[Πηγή της ερώτησης]
https://www.acwing.com/problem/content/3590/

[Περιγραφή Τίτλου]
Με δεδομένο ένα μη κατευθυνόμενο γράφημα και όλες τις ακμές του, προσδιορίστε εάν όλες οι κορυφές αυτού του γραφήματος είναι συνδεδεμένες.

【Μορφή εισαγωγής】
Η είσοδος περιέχει πολλά σύνολα δεδομένων.
Η πρώτη γραμμή κάθε συνόλου δεδομένων περιέχει δύο ακέραιους αριθμούς n και m, που αντιπροσωπεύουν τον αριθμό των σημείων και των ακμών του μη κατευθυνόμενου γραφήματος.
Οι επόμενες m γραμμές, κάθε γραμμή περιέχει δύο ακέραιους x, y, που υποδεικνύουν ότι το σημείο x και το σημείο y είναι συνδεδεμένα.
Τα σημεία αριθμούνται από το 1 έως το n.
Μπορεί να υπάρχει στην εικόναΔιπλη ακρηκαιΑυτο-βρόχος。

[Μορφή εξόδου]
Κάθε σύνολο δεδομένων εξάγει μία γραμμή και ένα αποτέλεσμα Εάν είναι συνδεδεμένες όλες οι κορυφές, βγάζετε ΝΑΙ, διαφορετικά βγάζετε ΟΧΙ.

【φασμα ΔΕΔΟΜΕΝΩΝ】
Η είσοδος περιέχει έως και 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+chained forward star]
● Πρότυπο αλγορίθμου 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