261. Graph Valid Tree
LeetCode
medium
оригинал: C#
#array
#csharp
#graph
#hash-table
#leetcode
#linked-list
#medium
#queue
#stack
#tree
У вас есть граф из n узлов, помеченных от 0 до n - 1. Вам даны целое число n и список рёбер, где edges[i] = [ai, bi] указывает на то, что существует неориентированное ребро между узлами ai и bi в графе.
Верните true, если рёбра данного графа образуют допустимое дерево, и false в противном случае.
Пример:
Input: n = 5, edges = [[0,1],[0,2],[0,3],[1,4]]
Output: true
C# решение
сопоставлено/оригиналusing System;
using System.Collections.Generic;
public class Solution {
public bool ValidTree(int n, int[][] edges) {
if (edges.Length != n - 1) {
return false;
}
List<int>[] adjList = new List<int>[n];
for (int i = 0; i < n; i++) {
adjList[i] = new List<int>();
}
foreach (var edge in edges) {
adjList[edge[0]].Add(edge[1]);
adjList[edge[1]].Add(edge[0]);
}
Dictionary<int, int> parent = new Dictionary<int, int> { { 0, -1 } };
Queue<int> queue = new Queue<int>();
queue.Enqueue(0);
while (queue.Count > 0) {
int node = queue.Dequeue();
foreach (int neighbor in adjList[node]) {
if (neighbor == parent[node]) {
continue;
}
if (parent.ContainsKey(neighbor)) {
return false;
}
parent[neighbor] = node;
queue.Enqueue(neighbor);
}
}
return parent.Count == n;
}
}C++ решение
auto-draft, проверить перед отправкой#include <bits/stdc++.h>
using namespace std;
// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
public bool ValidTree(int n, int[][] edges) {
if (edges.size() != n - 1) {
return false;
}
List<int>[] adjList = new List<int>[n];
for (int i = 0; i < n; i++) {
adjList[i] = new List<int>();
}
foreach (var edge in edges) {
adjList[edge[0]].push_back(edge[1]);
adjList[edge[1]].push_back(edge[0]);
}
unordered_map<int, int> parent = new unordered_map<int, int> { { 0, -1 } };
queue<int> queue = new queue<int>();
queue.Enqueue(0);
while (queue.size() > 0) {
int node = queue.Dequeue();
foreach (int neighbor in adjList[node]) {
if (neighbor == parent[node]) {
continue;
}
if (parent.count(neighbor)) {
return false;
}
parent[neighbor] = node;
queue.Enqueue(neighbor);
}
}
return parent.size() == n;
}
}Java решение
сопоставлено/оригиналimport java.util.*;
class Solution {
public boolean validTree(int n, int[][] edges) {
if (edges.length != n - 1) {
return false;
}
List<List<Integer>> adjList = new ArrayList<>();
for (int i = 0; i < n; i++) {
adjList.add(new ArrayList<>());
}
for (int[] edge : edges) {
adjList.get(edge[0]).add(edge[1]);
adjList.get(edge[1]).add(edge[0]);
}
Map<Integer, Integer> parent = new HashMap<>();
parent.put(0, -1);
Queue<Integer> queue = new LinkedList<>();
queue.add(0);
while (!queue.isEmpty()) {
int node = queue.poll();
for (int neighbor : adjList.get(node)) {
if (neighbor == parent.get(node)) {
continue;
}
if (parent.containsKey(neighbor)) {
return false;
}
parent.put(neighbor, node);
queue.add(neighbor);
}
}
return parent.size() == n;
}
}JavaScript решение
сопоставлено/оригиналclass Solution {
validTree(n, edges) {
if (edges.length !== n - 1) {
return false;
}
const adjList = Array.from({ length: n }, () => []);
for (const [A, B] of edges) {
adjList[A].push(B);
adjList[B].push(A);
}
const parent = { 0: -1 };
const queue = [0];
while (queue.length) {
const node = queue.shift();
for (const neighbor of adjList[node]) {
if (neighbor === parent[node]) {
continue;
}
if (neighbor in parent) {
return false;
}
parent[neighbor] = node;
queue.push(neighbor);
}
}
return Object.keys(parent).length === n;
}
}Python решение
сопоставлено/оригиналimport collections
from typing import List
class Solution:
def validTree(self, n: int, edges: List[List[int]]) -> bool:
if len(edges) != n - 1:
return False
adj_list = [[] for _ in range(n)]
for A, B in edges:
adj_list[A].append(B)
adj_list[B].append(A)
parent = {0: -1}
queue = collections.deque([0])
while queue:
node = queue.popleft()
for neighbour in adj_list[node]:
if neighbour == parent[node]:
continue
if neighbour in parent:
return False
parent[neighbour] = node
queue.append(neighbour)
return len(parent) == nGo решение
сопоставлено/оригиналpackage main
func validTree(n int, edges [][]int) bool {
if len(edges) != n-1 {
return false
}
adjList := make([][]int, n)
for _, edge := range edges {
adjList[edge[0]] = append(adjList[edge[0]], edge[1])
adjList[edge[1]] = append(adjList[edge[1]], edge[0])
}
parent := make(map[int]int)
parent[0] = -1
queue := []int{0}
for len(queue) > 0 {
node := queue[0]
queue = queue[1:]
for _, neighbor := range adjList[node] {
if neighbor == parent[node] {
continue
}
if _, found := parent[neighbor]; found {
return false
}
parent[neighbor] = node
queue = append(queue, neighbor)
}
}
return len(parent) == n
}Algorithm
1️⃣
Проверьте, что количество рёбер равно n - 1. Если нет, верните false.
2️⃣
Используйте итеративный обход в глубину (DFS) для проверки связности графа и отсутствия циклов. Создайте стек для хранения узлов для посещения и множество для отслеживания посещённых узлов. Начните с узла 0.
3️⃣
Если все узлы посещены и циклы не обнаружены, верните true. В противном случае, верните false.
😎
Вакансии для этой задачи
Показаны активные вакансии с пересечением по тегам задачи.
Активных вакансий пока нет.