기술나눔

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

[질문의 출처]
https://www.acwing.com/problem/content/3590/

[제목 설명]
무방향 그래프와 그 안에 있는 모든 간선이 주어지면 이 그래프의 모든 정점이 연결되어 있는지 확인합니다.

【입력 형식】
입력에는 여러 데이터 세트가 포함되어 있습니다.
각 데이터 세트의 첫 번째 줄에는 무방향 그래프의 점과 모서리 수를 나타내는 두 개의 정수 n과 m이 포함됩니다.
다음 m개 라인의 각 라인에는 두 개의 정수 x, y가 포함되어 있으며 이는 x 지점과 y 지점이 연결되어 있음을 나타냅니다.
포인트는 1부터 n까지 번호가 매겨져 있습니다.
사진에 있을수도 있어요이중 가장자리그리고자가 루프。

[출력 형식]
각 데이터 세트는 한 줄과 하나의 결과를 출력합니다. 모든 정점이 연결되면 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/솔루션/콘텐츠/124095/
https://blog.csdn.net/hnjzsyjyj/article/details/118736059
https://blog.csdn.net/hnjzsyjyj/article/details/139369904