Berbagi teknologi

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

[Sumber pertanyaan]
https://www.acwing.com/masalah/konten/3590/

[Deskripsi judul]
Diberikan suatu graf tak berarah dan semua sisi yang ada di dalamnya, tentukan apakah semua simpul pada graf tersebut terhubung.

【Masukkan format】
Inputnya berisi beberapa set data.
Baris pertama dari setiap kumpulan data berisi dua bilangan bulat n dan m, yang mewakili jumlah titik dan tepi grafik tidak berarah.
M baris berikutnya, setiap baris berisi dua bilangan bulat x,y, yang menunjukkan bahwa titik x dan titik y terhubung.
Poin diberi nomor dari 1 hingga n.
Mungkin ada di gambartepi gandaDanPutaran mandiri。

[Format output]
Setiap kumpulan data mengeluarkan satu baris dan satu hasil. Jika semua simpul terhubung, keluarannya YA, jika tidak, keluarannya TIDAK.

【rentang data】
Masukan berisi hingga 10 set data.
1≤n≤1000,
1≤m≤5000,
1≤x,y≤n

【Sampel masukan】
4 3
1 2
2 3
3 2
3 2
1 2
2 3

【Sampel keluaran】
TIDAK
YA

【Analisis Algoritma】
● “Dan cari koleksinya"Untuk detail implementasi kode, silakan lihat:https://blog.csdn.net/hnjzsyjyj/artikel/detail/126455868
● Prinsip penggunaan dfs untuk menentukan graf terhubung pada soal ini terletak pada “dfs harus mampu melintasi semua titik pada grafik terhubungJika suatu titik tidak dilalui berarti tidak terhubung.

[Kode algoritma: dfs+bintang maju berantai]
● templat algoritma dfs:https://blog.csdn.net/hnjzsyjyj/artikel/detail/118736059
● Untuk detail tentang bintang rantai maju, silakan lihat:https://blog.csdn.net/hnjzsyjyj/artikel/detail/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
*/

[Kode algoritma: dfs+matriks ketetanggaan]
● templat algoritma dfs:https://blog.csdn.net/hnjzsyjyj/artikel/detail/118736059
● Implementasi matriks ketetanggaan dari graf tak berbobot tak berarah:https://blog.csdn.net/hnjzsyjyj/artikel/detail/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
*/

【referensi】
https://www.acwing.com/solusi/konten/124095/
https://blog.csdn.net/hnjzsyjyj/artikel/detail/118736059
https://blog.csdn.net/hnjzsyjyj/artikel/detail/139369904