[BOJ]1260:DFSとBFS

14959 ワード
テキストリンク

💉質問内容


問題に答える

💉にゅうしゅつりょく


🧺入力
1行目は頂点の個数N(1≦N≦1000)、幹線の個数M(1≦M≦10000)、探索を開始する頂点の番号Vを与える.次のM行は、幹線接続の2つの頂点の番号を示します.2つの頂点の間に複数の幹線があります.入力された幹線は双方向です.
🧺しゅつりょく
1行目はDFSを実行した結果を出力し、2行目はBFSを実行した結果を出力する.Vから順にアクセスポイントを出力すればよい.

🔋サンプルI/O


🔮入力例1
4 5 1
1 2
1 3
1 4
2 4
3 4
🔮サンプル出力1
1 2 4 3
1 2 3 4
🔮入力例2
5 5 3
5 4
5 2
1 2
3 4
3 1
🔮サンプル出力2
3 1 2 5 4
3 1 4 2 5
🔮入力例3
1000 1 1000
999 1000
🔮サンプル出力3
1000 999
1000 999

💉もんだいぶんせき


🔋ぶんかつ


BFS, DFS

🔋難易度


シルバーII

💉問題を解く


🔋解法


この問題は、dfsとbfsを順番に実行するだけです.
注意点は、隣接するノードから開始する必要があります.

🔋ソースコード

#include <bits/stdc++.h>

constexpr int MAX = 1001;
int adj[MAX][MAX];

std::vector<int> dfs(int start, int N){
	std::vector<int>ans;
	
	std::stack<int>s;
	std::vector<bool> visit(N + 1, false);
	s.push(start);
	visit[start] = true;
	ans.push_back(start);
	
	while(!s.empty()){
		int x = s.top();
		s.pop();
		
		for(int i=1;i<=N;++i){
			if(!visit[i] && adj[x][i]){
				visit[i] = true;
				s.push(x);
				s.push(i);
				ans.push_back(i);
				break;
			}
		}
	}
	
	return ans;
}

std::vector<int> bfs(int start, int N){
	std::vector<int>ans;
	
	std::queue<int>q;
	std::vector<bool> visit(N + 1, false);
	q.push(start);
	visit[start] = true;
	ans.push_back(start);
	
	while(!q.empty()){
		int x = q.front();
		q.pop();
		
		for(int i=1;i<=N;++i){
			if(!visit[i] && adj[x][i]){
				visit[i] = true;
				q.push(i);
				ans.push_back(i);
			}
		}
	}
	
	return ans;
}

int main() {
	int M, N, S;
	std::cin >> N >> M >> S;
	for(int i=0;i<M;++i){
		int a, b;
		std::cin >> a >> b;
		adj[a][b] = 1;
		adj[b][a] = 1;
	}
	
	for(auto const& a : dfs(S, N)) std::cout << a << " ";
	std::cout << '\n';
	for(auto a : bfs(S, N)) std::cout << a << " ";
}
まずは11分ほどかかります
これはdfsとbfsを実行するだけの問題であり,非常に簡単である.

💉終了時..。


気になる部分があればコメントで質問しましょう~
Alamofire
雑誌式