ProblemSolving/1260.cpp at main · readable-ko/ProblemSolving · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include <bits/stdc++.h>
using namespace std ;
int vertax, edge, start_v ;

void bfs(vector<int> &arr, bool graph[1001][1001])
{
    queue<int> que ;
    que.push(start_v) ;

    while(!que.empty())
    {
        arr.push_back(que.front()) ;
        int now = que.front() ;
        que.pop() ;

        for(int i = 1 ; i <= vertax ; i++)
        {
            if(graph[now][i])
            {
                que.push(i) ;
                for(int j = 1 ; j <= vertax ; j++)
                {
                    graph[j][i] = false ;
                }
            }
            graph[i][now] = false ;
        }
    }

    arr.erase(unique(arr.begin(),arr.end()), arr.end()) ;
}

void dfs(vector<int> &arr, bool graph[1001][1001], int start_v)
{
    arr.push_back(start_v) ;
    for(int i = 1 ; i <= vertax ; i++)
        graph[i][start_v] = false ;

    for(int i = 1 ; i <= vertax ; i++)
    {
        if(graph[start_v][i]) dfs(arr, graph, i) ;
    }
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) ;
    cin >> vertax >> edge >> start_v ;
    int start, end ;
    bool Bgraph[1001][1001] ;
    bool Dgraph[1001][1001] ;
    fill(&Bgraph[0][0], &Bgraph[1000][1000], 0) ;
    fill(&Dgraph[0][0], &Dgraph[1000][1000], 0) ;

    for(int i = 0 ; i < edge ; i++)
    {
        cin >> start >> end ;
        Bgraph[start][end] = true ;
        Bgraph[end][start] = true ;
        Dgraph[start][end] = true ;
        Dgraph[end][start] = true ;
    }

    vector<int> BFS_arr, DFS_arr ;
    bfs(BFS_arr, Bgraph) ;
    dfs(DFS_arr, Dgraph, start_v) ;

    for(int it : DFS_arr)
        cout << it << " ";
    cout << "\n";

    for(int it : BFS_arr)
        cout << it << " ";
    cout << "\n";
}

/**
 * @brief
 * void bfs(int x){
    printf("%d ",x);
    bvisited[x]=true;
    queue<int> q;
    q.push(x);
    while(!q.empty()){
        int size = q.size();
        for(int i=0;i<size;i++){
            int curr = q.front();
            q.pop();
            for(int next:adj[curr]){
                if(!bvisited[next]){
                    bvisited[next]=true;
                    printf("%d ",next);
                    q.push(next);
                }
            }
        }
    }
}
 *
 */