Задача пробного раунда Яндекс Контеста https://contest.yandex.ru/yacup/contest/19036/problems/E/
Сеть компании состоит из серверов, каждый из которых имеет уникальный целочисленный идентификатор. N пар серверов соединены друг с другом. Соединённые серверы образуют кластеры: два сервера относятся к одному и тому же кластеру, если от одного из них можно добраться до другого, перемещаясь по связям. Периодически возникает необходимость скачать определённый файл на некоторый сервер. В сети работает сервис, аналогичный торрент-трекеру, который может сообщить, на каких серверах уже имеется необходимый файл. Проблема, однако, заключается в том, что любой сервер может скачивать файлы только с серверов в его кластере. Составьте программу, которая будет анализировать конфигурацию сети и сообщать, из каких источников определённый сервер может скачать необходимый файл.
Дальше приведу скриншот, т.к. сюда некорректно вставляется
Вот мой код, постарался понятнее его переписать Логика программы такая: Считываю связи между серверами, с помощью поиска в глубину ищу среди них узлы, после считываю с консоли запросы и сразу же смотрю, есть ли они в том же кластере, что и Xi. Есть 3 идеи на оптимизацию:
- При вводе связей сразу создавать подкластеры(A1,B1),(A2,B2)..., если A2 или B2 содержится в первом кластере то добавить B2 или A2 соответсвенно в кластер, потом ещё раз пройтись и объединить уже подкластеры, но не очень понятно как это сделать правильно, пока ещё размышляю.
- При считывании запросов можно сначала всё считать, потом объединить одинаковые Xi, ведь в условии не сказано что они не повторяются, но тогда надо как-то будет следить за порядком вывода, что в конечном итоге мне кажется не даст существенного ускорения
- Распараллелить программу? Кто-то в курсе, дают проверяющие машины несколько процессоров или нет?
using System;
using System.Collections.Generic;
using System.Linq;
using System.Diagnostics;
namespace Yandex2020_1
{
class Program
{
static void Main(string[] args)
{
int n = Convert.ToInt32(Console.ReadLine());
List< Tuple<int, int>> linkList = new List<Tuple<int, int>>();
HashSet<int> setNodes = new HashSet<int>();
HashSet<Node> nodes = new HashSet<Node>();
for (int i = 0; i < n; i++)
{
string[] nums_strings = Console.ReadLine().Split();
int a = Convert.ToInt32(nums_strings[0]);
int b = Convert.ToInt32(nums_strings[1]);
linkList.Add(new Tuple<int, int>(a, b));
setNodes.Add(a);setNodes.Add(b);
}
MyStopwatch stopWatch = new MyStopwatch();
foreach (int i in setNodes)
nodes.Add(new Node(i));
foreach(Tuple<int, int> tuple in linkList)
{
Node node = nodes.Where(p=>p.Name==tuple.Item1).ToList()[0];
node.AddChildren(nodes.Where(p => p.Name == tuple.Item2).ToList()[0]);
}
DepthFirstSearch dFS = new DepthFirstSearch();
HashSet<HashSet<int>> clusters=new HashSet<HashSet<int>>(); //Сет кластеров
Node nodeSearch= nodes.Where(x => !dFS.visited.Contains(x)).ToList().FirstOrDefault();
while(nodeSearch!=null)
{
clusters.Add(dFS.DFS(nodeSearch));
nodeSearch = nodes.Where(x => !dFS.visited.Contains(x)).ToList().FirstOrDefault();//берём первый непосещённый узел
}
int q = Convert.ToInt32(Console.ReadLine());
List<string> outS= new List<string>();
//поиск принадлежности к кластерам
for (int i = 0; i < q; i++)
{
string[] nums_strings = Console.ReadLine().Split();
int a = Convert.ToInt32(nums_strings[0]);
//ищем кластер в котором сервер, на который нужно скачать
HashSet<int> cluster = clusters.Where(x => x.Contains(a)).ToList()[0];
nums_strings = Console.ReadLine().Split();
int k = 0;
string temp = "";
//записываем все сервера, к которым есть доступ сразу в строку для вывода
foreach (string s in nums_strings)
{
if (cluster.Contains(Convert.ToInt32(s)))
{
k++;
temp += s+" ";
}
}
outS.Add(k.ToString()+" " + temp.Trim());
}
foreach (string s in outS)
Console.WriteLine(s);
}
}
public class MyStopwatch:Stopwatch
{
List<string> line =new List<string>();
public void Rec(string name)
{
TimeSpan ts = Elapsed;
string elapsedTime = String.Format("{0:00}:{1:00}:{2:00}.{3:00}",
ts.Hours, ts.Minutes, ts.Seconds,
ts.Milliseconds / 10);
line.Add(name + ": RunTime " + elapsedTime);
}
public void Write()
{
foreach(string s in line)
Console.WriteLine(s);
}
}
class Node : IComparable<Node>
{
/// Имя вершины.
public int Name { get; }
/// Список соседних вершин.
public List<Node> Children { get; }
public Node(int name)
{
Name = name;
Children = new List<Node>();
}
/// Добавляет новую соседнюю вершину.
/// bidirect->Неориентированое ребро
public Node AddChildren(Node node, bool bidirect = true)
{
Children.Add(node);
if (bidirect)
{
node.Children.Add(this);
}
return this;
}
public int CompareTo(Node comparePart)
{
// A null value means that this object is greater.
if (comparePart == null)
return 1;
else
return this.Name.CompareTo(comparePart.Name);
}
}
//обход
class DepthFirstSearch
{
// Список посещенных вершин
public HashSet<Node> visited= new HashSet<Node>();
// Путь из начальной вершины в целевую.
private HashSet<int> path;
public HashSet<int> DFS(Node start)
{
path = new HashSet<int>();
Search(start);
path.Add(start.Name);
return path;
}
private bool Search(Node node)
{
visited.Add(node);
foreach (var child in node.Children.Where(x => !visited.Contains(x)))
{
Search(child);
path.Add(child.Name);
}
return false;
}
}
}
Новый вариант
using System;
using System.Collections.Generic;
using System.Linq;
using System.Diagnostics;
namespace Yandex2020_1
{
class Program
{
static void Main(string[] args)
{
int n = int.Parse(Console.ReadLine());
List< Tuple<int, int>> linkList = new List<Tuple<int, int>>();
HashSet<int> setNodes = new HashSet<int>();
HashSet<Node> nodes = new HashSet<Node>();
for (int i = 0; i < n; i++)
{
string[] nums_strings = Console.ReadLine().Split();
int a = int.Parse(nums_strings[0]);
int b = int.Parse(nums_strings[1]);
linkList.Add(new Tuple<int, int>(a, b));
setNodes.Add(a);setNodes.Add(b);
}
foreach (int i in setNodes)
nodes.Add(new Node(i));
foreach(Tuple<int, int> tuple in linkList)
{
Node node = nodes.Where(p=>p.Name==tuple.Item1).First();
node.AddChildren(nodes.Where(p => p.Name == tuple.Item2).First());
}
DepthFirstSearch dFS = new DepthFirstSearch();
HashSet<HashSet<int>> clusters=new HashSet<HashSet<int>>(); //Сет кластеров
Node nodeSearch= nodes.Where(x => !dFS.visited.Contains(x)).FirstOrDefault();
while(nodeSearch!=null)
{
clusters.Add(dFS.DFS(nodeSearch));
nodeSearch = nodes.Where(x => !dFS.visited.Contains(x)).FirstOrDefault();//берём первый непосещённый узел
}
int q = int.Parse(Console.ReadLine());
List<string> outS= new List<string>();
//поиск принадлежности к кластерам
for (int i = 0; i < q; i++)
{
int a = int.Parse(Console.ReadLine().Split()[0]);
//ищем кластер в котором сервер, на который нужно скачать
HashSet<int> cluster = clusters.Where(x => x.Contains(a)).ToList().First();
string[] nums_strings = Console.ReadLine().Split();
int k = 0;
string temp = "";
//записываем все сервера, к которым есть доступ сразу в строку для вывода
foreach (string s in nums_strings)
{
if (cluster.Contains(int.Parse(s)))
{
k++;
temp += s+" ";
}
}
outS.Add(k+" " + temp.Trim());
}
foreach (string s in outS)
Console.WriteLine(string.Join(Environment.NewLine, s));
}
}
class Node : IComparable<Node>
{
/// Имя вершины.
public int Name { get; }
/// Список соседних вершин.
public List<Node> Children { get; }
public Node(int name)
{
Name = name;
Children = new List<Node>();
}
/// Добавляет новую соседнюю вершину.
/// bidirect->Неориентированое ребро
public Node AddChildren(Node node, bool bidirect = true)
{
Children.Add(node);
if (bidirect)
{
node.Children.Add(this);
}
return this;
}
public int CompareTo(Node comparePart)
{
// A null value means that this object is greater.
if (comparePart == null)
return 1;
else
return this.Name.CompareTo(comparePart.Name);
}
}
//обход
class DepthFirstSearch
{
// Список посещенных вершин
public HashSet<Node> visited= new HashSet<Node>();
// Путь из начальной вершины в целевую.
private HashSet<int> path;
public HashSet<int> DFS(Node start)
{
path = new HashSet<int>();
Search(start);
path.Add(start.Name);
return path;
}
private bool Search(Node node)
{
visited.Add(node);
foreach (var child in node.Children.Where(x => !visited.Contains(x)))
{
Search(child);
path.Add(child.Name);
}
return false;
}
}
}
foreach (string s in outS) Console.WriteLine(s);можно преобразовать в вот такойConsole.WriteLine(string.Join(Environment.NewLine, outS). Но это на ваш вкус, просто делюсь. Плюс преобразования в том, что вызов операции вывода в консоль будет один, а не много. Минус в том, что в памяти появится большая строка, содержащая все строки из массива. 2)Convert.ToInt32можно заменить наint.Parseв вашем случае, потому что исходные данные -string.nodes.Where(..).ToList()[0]можно заменить наnodes.Where(...).First()4)int q = Convert.ToInt32(Console.ReadLine());- посмотрите безотказный ввод числа, можно сделать красиво. 5)outS.Add(k.ToString()+" " + temp.Trim());- в операциях конкатенации вызывать явно.ToString()не нужно, он будет вызван неявно автоматически..ToList().FirstOrDefault()тоже можно заменить на.FirstOrDefault(). Работать должно быстрее.За остальное спасибо тоже, но всё равно не хватает времени, кажется проблема в самой концепции. Теперь как ни странно памяти меньше ест, было TL 1.58s 23.09Mb теперь 1.586s 21.95Mb Памяти там вообще с запасом у меня я вижу, 256 мб же по условиям доступно
– Петр Иванов Sep 23 '20 at 13:03foreach (string s in outS) Console.WriteLine(string.Join(Environment.NewLine, s));ахаха? вот так надо:Console.WriteLine(string.Join(Environment.NewLine, outS));, без цикла :) – aepot Sep 23 '20 at 13:33var list = new List<int>(n);– Andrew Stop_RU_war_in_UA Sep 23 '20 at 13:36optimize codeв конфигурации сборки. – aepot Sep 23 '20 at 15:04