Mail.ruПочтаМой МирОдноклассникиВКонтактеИгрыЗнакомстваНовостиКалендарьОблакоЗаметкиВсе проекты

Помогите пожалуйста с написанием кода на с#, завтра сдача

Aaron Smith Ученик (79), на голосовании 2 дня назад
Имеется и населенных пунктов, перенумерованных от 1 до п. Некоторые пары пунктов
соединены дорогами. Определить, можно ли попасть по этим дорогам из 1-го пункта в п-й. Информация о дорогах задается в виде
последовательности пар чисел i и ј (i < j), указывающих, что і-й и ј-й пункты соединены дорогой;
признак конца этой
последовательности — пара нулей.
Голосование за лучший ответ
Uzi Uzu Гуру (3214) 1 месяц назад
 using System; 
using System.Collections.Generic;

class Program
{
static void Main()
{
Console.Write("Введите количество пунктов n: ");
int n = int.Parse(Console.ReadLine());

// Создаем список смежности
List<int>[] graph = new List<int>[n + 1];
for (int i = 1; i <= n; i++)
graph[i] = new List<int>();

// Считываем дороги
while (true)
{
Console.Write("Введите пару пунктов (i j) или 0 0 для завершения: ");
string[] input = Console.ReadLine().Split();
int i = int.Parse(input[0]);
int j = int.Parse(input[1]);

if (i == 0 && j == 0) break;

// Добавляем ребра в обоих направлениях
graph[i].Add(j);
graph[j].Add(i);
}

// Проверяем достижимость через поиск в ширину
bool[] visited = new bool[n + 1];
Queue<int> queue = new Queue<int>();

queue.Enqueue(1);
visited[1] = true;

while (queue.Count > 0)
{
int current = queue.Dequeue();

foreach (int next in graph[current])
{
if (!visited[next])
{
visited[next] = true;
queue.Enqueue(next);
}
}
}

if (visited[n])
Console.WriteLine("Можно попасть из 1-го в n-й пункт");
else
Console.WriteLine("Нельзя попасть из 1-го в n-й пункт");
}
}
Этот код:

Создает граф через список смежности
Считывает пары соединенных пунктов
Использует поиск в ширину для проверки достижимости n-го пункта из 1-го
Выводит результат

Пример использования:

 Введите количество пунктов n: 4 
Введите пару пунктов (i j) или 0 0 для завершения: 1 2
Введите пару пунктов (i j) или 0 0 для завершения: 2 3
Введите пару пунктов (i j) или 0 0 для завершения: 3 4
Введите пару пунктов (i j) или 0 0 для завершения: 0 0
Можно попасть из 1-го в n-й пункт
Jurijus ZaksasИскусственный Интеллект (449399) 1 месяц назад
 List<int>[] graph = new List<int>[n + 1];  
graph[i].Add(j);
Это как, родной? graph[i] вернет тебе некий int. У int по-твоему есть метод Add? Я понимаю, что это тебе тупой ИИ накропал, но нельзя же самому быть тупее, чем ИИ, и тупо за ним копипастить...
Jurijus Zaksas Искусственный Интеллект (449399) 1 месяц назад
Ну хотя бы так:

 public class GraphNode<T> where T: IEquatable<T> 
{
private readonly T val;
private readonly bool bidirectional;
private readonly Dictionary<T, GraphNode<T>> parent;
private HashSet<GraphNode<T>> links = new HashSet<GraphNode<T>>();
public T Value { get => val; }
public bool Bidirectional { get => bidirectional; }
public GraphNode(Dictionary<T, GraphNode<T>> _Parent, T _Value, bool _Bidirectional = false)
{
val = _Value;
bidirectional = _Bidirectional;
parent = _Parent;
}
public void AddLink(T _ToValue, bool _PreventRecursion = false)
{
if (!parent.TryGetValue(_ToValue, out GraphNode<T> TargetNode))
throw new Exception($"Link to {_ToValue} cannot be added - a corresponding node does not exist");
if (links.Contains(TargetNode))
throw new Exception($"Link to {_ToValue} cannot be added as it already exists");
links.Add(TargetNode);
if (!_PreventRecursion && bidirectional)
TargetNode.AddLink(Value, true);
}

private bool FindRoute(T _ToValue, HashSet<GraphNode<T>> _Visited)
{
if (_Visited.Contains(this))
return false;
_Visited.Add(this);
bool Result = Value.Equals(_ToValue);
foreach (GraphNode<T> Node in links)
Result |= Node.FindRoute(_ToValue, _Visited);
return Result;
}

public bool RouteExists(T _ToValue)
{
return FindRoute(_ToValue, new HashSet<GraphNode<T>>());
}
}

public class Graph<T> : Dictionary<T, GraphNode<T>> where T : IEquatable<T>
{
private readonly bool bidirectional;
public bool Bidirectional { get => bidirectional; }
public Graph(bool _Bidirectional)
{
bidirectional = _Bidirectional;
}
public void Add(T _Value)
{
base.Add(_Value, new GraphNode<T>(this, _Value, Bidirectional));
}
public bool RouteExists(T _FromValue, T _ToValue) => this[_FromValue].RouteExists(_ToValue);
}


internal class Program
{
static void Main(string[] args)
{
int n = int.Parse(Console.ReadLine());
Graph<int> SteffiGraff = new Graph<int>(true);
for (int i = 1; i <= n; i++)
SteffiGraff.Add(i);
int[] Links = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
for (int i = 0; i < Links.Length; i += 2)
SteffiGraff[Links[i]].AddLink(Links[i + 1]);
Console.WriteLine(SteffiGraff.RouteExists(1, n));
}
}
Похожие вопросы