Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- using System;
- using System.Collections;
- using System.Collections.Generic;
- using System.Linq;
- using System.Text;
- namespace mainSolution
- {
- class Input
- {
- private static IEnumerator<string> getin()
- {
- while (true)
- foreach (string s in Console.ReadLine().Split().Where(x => x.Length > 0))
- yield return s;
- }
- private IEnumerator<string> inp = getin();
- public string GetString() { inp.MoveNext(); return inp.Current; }
- public int GetInt() { return int.Parse(GetString()); }
- public long GetLong() { return long.Parse(GetString()); }
- public double GetDouble() { return double.Parse(GetString()); }
- }
- class TreeEnumerator : IEnumerator<int>
- {
- int level = 0;
- List<int> distance;
- int ptr = -1;
- public TreeEnumerator(List<int> distance)
- {
- this.distance = distance;
- }
- public void Dispose() { }
- object IEnumerator.Current => throw new NotImplementedException();
- public int Current
- {
- get
- {
- if ( level == -1 || level >= distance.Count)
- throw new InvalidOperationException();
- return ptr + 1;
- throw new InvalidOperationException();
- }
- }
- public bool MoveNext()
- {
- int k = ptr + 1;
- while (k < distance.Count)
- if (distance[k] == level)
- {
- ptr = k;
- return true;
- }
- else
- k++;
- level++;
- k = 0;
- while (k < distance.Count)
- if (distance[k] == level)
- {
- ptr = k;
- return true;
- }
- else
- k++;
- return false;
- }
- public void Reset()
- {
- level = -1;
- }
- }
- class Tree
- {
- public List<List<int>> g = new List<List<int>>();
- private List<int> parent = new List<int> ();
- private List<bool> used = new List<bool> ();
- private List<int> distance = new List<int>();
- private int size = 0;
- private int capacity = 0;
- bool isChanged = false;
- int sourse = 0;
- public IEnumerator<int> GetEnumerator()
- {
- if (isChanged)
- dfs(sourse);
- isChanged = false;
- return new TreeEnumerator(distance);
- }
- void dfs(int v)
- {
- used[v] = true;
- for (int i = 0; i < g[v].Count; ++i)
- {
- int to = g[v][i];
- if (!used[to])
- {
- parent[to] = v;
- distance[to] = distance[v] + 1;
- dfs(to);
- }
- }
- }
- public Tree() { }
- public Tree(int size)
- {
- setSize(size);
- Initialize();
- isChanged = true;
- }
- public int Sourse
- {
- get { return sourse; }
- set
- {
- distance[sourse] = -1;
- distance[value - 1] = 0;
- sourse = value - 1;
- }
- }
- public int Size
- {
- get { return size; }
- set { setSize(value); }
- }
- private void clearTree(int size)
- {
- for(int i = size; i < this.size; ++i)
- {
- g[i] = new List<int>();
- parent[i] = -1;
- used[i] = false;
- distance[i] = -1;
- }
- distance[sourse] = 0;
- }
- private void reset(int size)
- {
- for (int i = 0; i < capacity; ++i)
- {
- used[i] = false;
- parent[i] = -1;
- distance[i] = -1;
- }
- distance[sourse] = 0;
- }
- public void setSize(int size)
- {
- //this.size = size;
- if (capacity > size)
- {
- clearTree(size);
- isChanged = true;
- }
- else
- {
- int newCapacity = 1;
- while (newCapacity < size)
- newCapacity *= 2;
- Initialize(capacity, newCapacity);
- capacity = newCapacity;
- }
- this.size = size;
- }
- private void Initialize()
- {
- for (int i = 0; i < capacity; i++)
- {
- g.Add(new List<int>());
- parent.Add(new int());
- used.Add(new bool());
- distance.Add(new int());
- used[i] = false;
- parent[i] = -1;
- distance[i] = -1;
- }
- distance[sourse] = 0;
- }
- private void Initialize(int a, int b)
- {
- for (int i = a; i < b; i++)
- {
- g.Add(new List<int>());
- parent.Add(new int());
- used.Add(new bool());
- distance.Add(new int());
- used[i] = false;
- parent[i] = -1;
- distance[i] = -1;
- }
- distance[sourse] = 0;
- }
- public void Add(int v, int to)
- {
- v--;to--;
- g[v].Add(new int());
- g[v][g[v].Count - 1] = to;
- isChanged = true;
- }
- public void Print()
- {
- for (int i = 0; i < size; i++)
- {
- for (int j = 0; j < g[i].Count; j++)
- {
- Console.WriteLine($"{i + 1} {g[i][j] + 1}");
- }
- }
- }
- }
- static class Program
- {
- static void Main(string[] args)
- {
- Input cin = new Input();
- Tree tree = new Tree();
- tree.setSize(5);
- tree.Sourse = 2;
- tree.Add(2, 1);
- tree.Add(2, 3);
- tree.Add(3, 4);
- tree.Add(4, 5);
- foreach(var v in tree)
- Console.WriteLine(v);
- }
- }
- }
Add Comment
Please, Sign In to add comment