DFS 깊이 우선 탐색

 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cstring>
#define xx first
#define yy second
 
using namespace std;
using i64 = long long;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;

bool visited[10005];
vector <int> adj[10005];

void dfs(int curr)
{
    visited[curr] = true;
    printf("%d ", curr);
    
    for (int next : adj[curr])
    {
        if (!visited[next])
            dfs(next);
    }
}

int main() 
{
    int n, m, v;
    scanf("%d %d %d", &n, &m, &v);
    
    for (int i = 0; i < m; i++)
    {
        int u, v;
        scanf("%d %d", &u, &v);
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    
    for (int i = 1; i <= n; i++)
        sort(adj[i].begin(), adj[i].end());
    
    
    memset(visited, false, sizeof(visited));
    dfs(v);
    
    return 0;
}

 

 

---

 

 

 

끊어진? 새로운 그래프까지 확인하는 부분

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
 
using namespace std;
using i64 = long long;

class Graph {
public:
    int N;
    vector<vector <int>> adj;
    vector<bool> visited;
    
    Graph() : N(0) {}
    Graph(int n) : N(n) {
        adj.resize(N);
        visited.resize(N);
    }
    
    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    
    void sortList() {
        for (int i = 0; i < N; i++)
        {
            for (int i = 0; i < N; i++)
                sort(adj[i].begin(), adj[i].end());
        }
    }
    
    int dfsAll()
    {
        int components = 0;
        fill(visited.begin(), visited.end(), false);
        
        for (int i = 0; i < N; i++)
        {
            if (!visited[i])
            {
                cout << "new DFS begin" << endl;
                dfs(i);
                components++;
            }
        }
        
        return components;
    }
    
    void dfs()
    {
        fill(visited.begin(), visited.end(), false);
        dfs(0);
    }
private:
    void dfs(int curr)
    {
        visited[curr] = true;
        cout << "node " << curr << " visited " << endl;
        for (int next: adj[curr])
            if (!visited[next]) dfs(next);
    }
};
 
int main() {
    Graph G(9);
    G.addEdge(0, 1);
    G.addEdge(0, 2);
    G.addEdge(1, 3);
    G.addEdge(1, 5);
    G.addEdge(3, 4);
    G.addEdge(4, 5);
    G.addEdge(2, 6);
    G.addEdge(2, 8);
    G.addEdge(6, 7);
    G.addEdge(6, 8);
    G.sortList();
    G.dfsAll();
    
    return 0;
}