1260 DFS와 BFS/11724 연결요소의 개수

(1)DFS와 BFS

https://www.acmicpc.net/problem/1260

1260번: DFS와 BFS

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;
vector<int> graph[1001];
vector<bool> visited(1001, false);

void DFS(int ver) {
    cout << ver<<" ";
    visited[ver] = true;
    for (int i = 0; i < graph[ver].size(); i++) {
        int next = graph[ver][i];
        if (visited[next])
            continue;
        DFS(next);

    }
    
}

void BFS(int start, int v) {
    queue<int> q;
    q.push(start);
    visited[start] = true;
    cout << start << " ";
    while (!q.empty()) {
        int qSize = q.size();
        for (int i = 0; i < qSize; i++) {
            int ver = q.front();
            q.pop();


            for (int i = 0; i < graph[ver].size(); i++) {
                int adjv = graph[ver][i];
                if (!visited[adjv]) {
                    q.push(adjv);
                    visited[adjv] = true;
                    cout << adjv << " ";
                }

            }
        }

    }
    
    


}
 int main() {
    cin.tie(NULL);
    cin.sync_with_stdio(false);
    cout.tie(NULL);


    int v, e, startv;
    cin >> v >> e >> startv;

    for (int i = 0; i < e; i++) {
        int v1, v2;
        cin >> v1 >> v2;
        graph[v1].push_back(v2);
        graph[v2].push_back(v1);
    }
    for (int i = 1; i <= v; i++) {		//정점이 작은 것부터 방문하도록
        sort(graph[i].begin(), graph[i].end());
    }

    DFS(startv);

    cout << "\n";


    for (int i = 1; i <= v; i++) {
        visited[i] = false;
    }

    BFS(startv, v);
    
    return 0;

}

 

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;
vector<int> graph[1001];
vector<bool> visited(1001, false);

void DFS(int ver) {
    cout << ver << " ";
    visited[ver] = true;
    for (int i = 0; i < graph[ver].size(); i++) {
        int next = graph[ver][i];
        if (visited[next])
            continue;
        DFS(next);

    }

}

void BFS(int start, int v) {
    queue<int> q;
    q.push(start);
    visited[start] = true;
    while (!q.empty()) {
        int ver = q.front();
        q.pop();
        cout << ver << " ";
        for (int i = 0; i < graph[ver].size(); i++) {
            int adjv = graph[ver][i];
            if (!visited[adjv]) {
                q.push(adjv);
                visited[adjv] = true;
            }

        }

    }




}
int main() {
    cin.tie(NULL);
    cin.sync_with_stdio(false);
    cout.tie(NULL);


    int v, e, startv;
    cin >> v >> e >> startv;

    for (int i = 0; i < e; i++) {
        int v1, v2;
        cin >> v1 >> v2;
        graph[v1].push_back(v2);
        graph[v2].push_back(v1);
    }
    for (int i = 1; i <= v; i++) {      //정점이 작은 것부터 방문하도록
        sort(graph[i].begin(), graph[i].end());
    }

    DFS(startv);

    cout << "\n";


    for (int i = 1; i <= v; i++) {
        visited[i] = false;
    }

    BFS(startv, v);

    return 0;

}

참고 사이트

1. DFS 개념

https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=ndb796&logNo=221230945092 

16. 깊이 우선 탐색(DFS)

2. c++ /graph를 벡터로 

유사 코드

https://hyunah-home.tistory.com/6

백준/ 1260번(DFS와 BFS)/ C++ ; Vector와 sort함수 사용

 

 

(2) 11724 연결 요소의 개수

https://www.acmicpc.net/problem/11724

11724번: 연결 요소의 개수

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;
vector<int> graph[1001];
vector<bool> visited(1001, false);
int cnt = 0;



void BFS(int start, int v) {
    queue<int> q;
    q.push(start);
    visited[start] = true;
    
    while (!q.empty()) {
        int ver = q.front();
        q.pop();
        //cout << ver << " ";
        cnt++;
        for (int i = 0; i < graph[ver].size(); i++) {
            int adjv = graph[ver][i];
            if (!visited[adjv]) {
                q.push(adjv);
                visited[adjv] = true;
            }

        }

    }




}
int main() {
    cin.tie(NULL);
    cin.sync_with_stdio(false);
    cout.tie(NULL);


    int v, e;
    cin >> v >> e ;
    int connectedN = 0;

    for (int i = 0; i < e; i++) {
        int v1, v2;
        cin >> v1 >> v2;
        graph[v1].push_back(v2);
        graph[v2].push_back(v1);
    }
    for (int i = 1; i <= v; i++) {      //정점이 작은 것부터 방문하도록
        sort(graph[i].begin(), graph[i].end());
    }
    for (int s = 1; s <= v; s++) {
        if (!visited[s]) {
            BFS(s,v);
            connectedN++;
        }
    }

    
    cout << connectedN;
    return 0;

}