Infiniti_Inter

Невозможно...

Oct 11th, 2019
148
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C# 6.41 KB | None | 0 0
  1. using System;
  2. using System.Collections;
  3. using System.Collections.Generic;
  4. using System.Linq;
  5. using System.Text;
  6.  
  7. namespace mainSolution
  8. {
  9.     class Input
  10.     {
  11.         private static IEnumerator<string> getin()
  12.         {
  13.             while (true)
  14.                 foreach (string s in Console.ReadLine().Split().Where(x => x.Length > 0))
  15.                     yield return s;
  16.         }
  17.  
  18.         private IEnumerator<string> inp = getin();
  19.  
  20.         public string GetString() { inp.MoveNext(); return inp.Current; }
  21.         public int GetInt() { return int.Parse(GetString()); }
  22.         public long GetLong() { return long.Parse(GetString()); }
  23.         public double GetDouble() { return double.Parse(GetString()); }
  24.     }
  25.  
  26.  
  27.     class TreeEnumerator : IEnumerator<int>
  28.     {
  29.         int level = 0;
  30.         List<int> distance;
  31.         int ptr = -1;
  32.         public TreeEnumerator(List<int> distance)
  33.         {
  34.             this.distance = distance;
  35.         }
  36.         public void Dispose() { }
  37.         object IEnumerator.Current => throw new NotImplementedException();
  38.         public int Current
  39.         {
  40.             get
  41.             {
  42.                 if ( level == -1 || level >= distance.Count)
  43.                     throw new InvalidOperationException();
  44.                 return ptr + 1;
  45.                 throw new InvalidOperationException();
  46.             }
  47.         }
  48.  
  49.         public bool MoveNext()
  50.         {
  51.             int k = ptr + 1;
  52.             while (k < distance.Count)
  53.                 if (distance[k] == level)
  54.                 {
  55.                     ptr = k;
  56.                     return true;
  57.                 }
  58.                 else
  59.                     k++;
  60.             level++;
  61.             k = 0;
  62.             while (k < distance.Count)
  63.                 if (distance[k] == level)
  64.                 {
  65.                     ptr = k;
  66.                     return true;
  67.                 }
  68.                 else
  69.                     k++;
  70.             return false;
  71.         }
  72.         public void Reset()
  73.         {
  74.             level = -1;
  75.         }
  76.     }
  77.     class Tree
  78.     {
  79.         public List<List<int>> g = new List<List<int>>();
  80.         private List<int> parent = new List<int> ();
  81.         private List<bool> used = new List<bool> ();
  82.         private List<int> distance = new List<int>();
  83.  
  84.         private int size = 0;
  85.         private int capacity = 0;
  86.         bool isChanged = false;
  87.         int sourse = 0;
  88.         public IEnumerator<int> GetEnumerator()
  89.         {
  90.             if (isChanged)
  91.                 dfs(sourse);
  92.             isChanged = false;
  93.             return new TreeEnumerator(distance);
  94.         }
  95.  
  96.  
  97.         void dfs(int v)
  98.         {
  99.             used[v] = true;
  100.             for (int i = 0; i < g[v].Count; ++i)
  101.             {
  102.                 int to = g[v][i];
  103.                 if (!used[to])
  104.                 {
  105.                     parent[to] = v;
  106.                     distance[to] = distance[v] + 1;
  107.                     dfs(to);
  108.                 }
  109.             }
  110.         }
  111.  
  112.         public Tree() { }
  113.         public Tree(int size)
  114.         {
  115.             setSize(size);
  116.             Initialize();
  117.             isChanged = true;
  118.         }
  119.  
  120.         public int Sourse
  121.         {
  122.             get { return sourse; }
  123.             set
  124.             {
  125.                 distance[sourse] = -1;
  126.                 distance[value - 1] = 0;
  127.                 sourse = value - 1;
  128.             }
  129.         }
  130.         public int Size
  131.         {
  132.             get { return size; }
  133.             set { setSize(value); }
  134.         }
  135.         private void clearTree(int size)
  136.         {
  137.             for(int i = size; i < this.size; ++i)
  138.             {
  139.                 g[i] = new List<int>();
  140.                 parent[i] = -1;
  141.                 used[i] = false;
  142.                 distance[i] = -1;
  143.             }
  144.             distance[sourse] = 0;
  145.         }
  146.  
  147.  
  148.  
  149.         private void reset(int size)
  150.         {
  151.             for (int i = 0; i < capacity; ++i)
  152.             {
  153.                 used[i] = false;
  154.                 parent[i] = -1;
  155.                 distance[i] = -1;
  156.             }
  157.             distance[sourse] = 0;
  158.         }
  159.         public void setSize(int size)
  160.         {
  161.             //this.size = size;
  162.             if (capacity > size)
  163.             {
  164.                 clearTree(size);
  165.                 isChanged = true;
  166.             }
  167.             else
  168.             {
  169.                 int newCapacity = 1;
  170.                 while (newCapacity < size)
  171.                     newCapacity *= 2;
  172.                 Initialize(capacity, newCapacity);
  173.                 capacity = newCapacity;
  174.             }
  175.             this.size = size;
  176.         }
  177.         private void Initialize()
  178.         {
  179.             for (int i = 0; i < capacity; i++)
  180.             {
  181.                 g.Add(new List<int>());
  182.                 parent.Add(new int());
  183.                 used.Add(new bool());
  184.                 distance.Add(new int());
  185.                 used[i] = false;
  186.                 parent[i] = -1;
  187.                 distance[i] = -1;
  188.             }
  189.             distance[sourse] = 0;
  190.         }
  191.         private void Initialize(int a, int b)
  192.         {
  193.             for (int i = a; i < b; i++)
  194.             {
  195.                 g.Add(new List<int>());
  196.                 parent.Add(new int());
  197.                 used.Add(new bool());
  198.                 distance.Add(new int());
  199.                 used[i] = false;
  200.                 parent[i] = -1;
  201.                 distance[i] = -1;
  202.             }
  203.             distance[sourse] = 0;
  204.         }
  205.  
  206.         public void Add(int v, int to)
  207.         {
  208.             v--;to--;
  209.             g[v].Add(new int());
  210.             g[v][g[v].Count - 1] = to;
  211.             isChanged = true;
  212.         }
  213.  
  214.         public void Print()
  215.         {
  216.             for (int i = 0; i < size; i++)
  217.             {
  218.                 for (int j = 0; j < g[i].Count; j++)
  219.                 {
  220.                     Console.WriteLine($"{i + 1} {g[i][j] + 1}");
  221.                 }
  222.             }
  223.         }
  224.  
  225.  
  226.  
  227.     }
  228.     static class Program
  229.     {
  230.  
  231.         static void Main(string[] args)
  232.         {
  233.             Input cin = new Input();
  234.             Tree tree = new Tree();
  235.             tree.setSize(5);
  236.             tree.Sourse = 2;
  237.             tree.Add(2, 1);
  238.             tree.Add(2, 3);
  239.             tree.Add(3, 4);
  240.             tree.Add(4, 5);
  241.            
  242.             foreach(var v in tree)
  243.                 Console.WriteLine(v);
  244.         }
  245.        
  246.  
  247.  
  248.     }
  249. }
Add Comment
Please, Sign In to add comment