[白俊]木を探していた両親(11725)

25398 ワード
白駿 BFS DFS ジャワ Java アルゴリズム#アルゴリズム# 木。 backjoon テキストリンク

質問する


[伯俊]木の両親を探す
根のない木をあげます.ツリーのルートディレクトリが1の場合、各ノードの親ノードを解くプログラムを作成します.

入力


第1行は、ノード数N(2≦N≦100000)を与える.2行目から、ツリーに接続された2つの頂点がN−1行に与えられる.

しゅつりょく


1行目からN-1行目まで、各ノードの親ノード番号が2番目のノードから順次出力されます.

解説


DFSとBFSの2つの方法で説明してみましたが,これは今後の応用問題のために準備された基礎的な問題だと思います.
メモリはBFSDFSである.

に答える


DFS

import java.util.*;
import java.io.*;

public class Main {
	static int N;
	static int[] parent;
	static boolean[] visited;
	static ArrayList<Integer>[] graph;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		N = Integer.parseInt(br.readLine());
	
		parent = new int[N+1];
		visited = new boolean[N+1];
		graph = new ArrayList[N+1];
		
		for (int i = 0; i <= N; i++) {
			graph[i] = new ArrayList<>();
		}
		
		for (int i = 0; i < N-1; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			
			int v = Integer.parseInt(st.nextToken());
			int u = Integer.parseInt(st.nextToken());
			
			graph[v].add(u);
			graph[u].add(v);
		}
		
		visited[1] = true;
		
		dfs(1);
		
		StringBuilder sb = new StringBuilder();
		
		for(int i = 2; i <= N; i++) {
			sb.append(parent[i]).append("\n");
		}
		
		System.out.println(sb.toString());
	}
	
	public static void dfs(int u) {
		for(int v : graph[u]) {
			if(!visited[v]) {
				parent[v] = u;
				visited[v] = true;
				dfs(v);
			}
		}
	}
}

BFS

import java.util.*;
import java.io.*;

public class Main {
	static int N;
	static ArrayList<Integer>[] graph;
	static Queue<Integer> queue;
	static boolean[] visited;
	static int[] parent;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		N = Integer.parseInt(br.readLine());

		graph = new ArrayList[N + 1];
		queue = new LinkedList<>();
		visited = new boolean[N + 1];
		parent = new int[N + 1];
		
		for (int i = 0; i <= N; i++) {
			graph[i] = new ArrayList<>();
		}

		for (int i = 0; i < N - 1; i++) {
			st = new StringTokenizer(br.readLine(), " ");

			int v = Integer.parseInt(st.nextToken());
			int u = Integer.parseInt(st.nextToken());

			graph[v].add(u);
			graph[u].add(v);
		}

		queue.add(1);

		while (!queue.isEmpty()) {
			int u = queue.poll();

			for (int v : graph[u]) {
				if (!visited[v]) {
					visited[v] = true;
					parent[v] = u;
					queue.add(v);
				}
			}
		}
		
		StringBuilder sb = new StringBuilder();
		
		for(int i = 2; i <= N; i++) {
			sb.append(parent[i]).append("\n");
		}
		
		System.out.println(sb.toString());
	}
}
ボタンに枠線を設定する例
[アプリケーション編]会員管理ページの作成(設計書編)