using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Zad1
{
    class Program
    {
        static void Main(string[] args)
        {
            Kopiec K1 = new Kopiec();
            K1.Dodaj(1);
            K1.Dodaj(3);
            K1.Dodaj(5);
            K1.Dodaj(1);
            K1.Dodaj(7);
            K1.Dodaj(2);
            K1.Dodaj(9);
            K1.Dodaj(12);
            K1.Dodaj(0);

            K1.wyświetl();

            if(K1.sprawdzCzyKopiecMinimalny())
                Console.WriteLine("Kopiec minimalny");
            else
                Console.WriteLine("To sie nie wyświetli");

            Console.ReadKey();
        }

        class Kopiec
        {
            int wielkość = 0;
            int[] tablica = new int[30];

            public Kopiec()
            {
            }

            public void Dodaj(int war)
            {
                if (wielkość + 1 < tablica.Length)
                {
                    tablica[wielkość] = war;
                    wielkość++;
                }
                buduj();
            }

            public void napraw(int i)
            {
                int d1 = i * 3 + 1;
                int d2 = i * 3 + 2;
                int d3 = i * 3 + 3;
                int naj = i;
                if (d1 < wielkość && tablica[d1] < tablica[naj])
                {
                    naj = d1;
                }
                if (d2 < wielkość && tablica[d2] < tablica[naj])
                {
                    naj = d2;
                }
                if (d3 < wielkość && tablica[d3] < tablica[naj])
                {
                    naj = d3;
                }
                if (naj != i)
                {
                    int tmp = tablica[i];
                    tablica[i] = tablica[naj];
                    tablica[naj] = tmp;
                    napraw(naj);
                }
            }

            public void buduj()
            {
                for (int i = wielkość / 2; i >= 0; i--)
                {
                    napraw(i);
                }
            }

            public void wyświetl()
            {
                for (int i = 0; i < wielkość; i++)
                {
                    Console.Write(tablica[i] + " ");
                }
                Console.WriteLine();
            }

            public bool sprawdzCzyKopiecMinimalny()
            {
                for (int i = wielkość / 2; i >= 0; i--)
                {
                    int d1 = i * 3 + 1;
                    int d2 = i * 3 + 2;
                    int d3 = i * 3 + 3;
                    if (d1 < wielkość && tablica[d1] < tablica[i])
                    {
                        return false;
                    }
                    if (d2 < wielkość && tablica[d2] < tablica[i])
                    {
                        return false;
                    }
                    if (d3 < wielkość && tablica[d3] < tablica[i])
                    {
                        return false;
                    }
                }
                return true;
            }
        }
    }
}

///////

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Zad2_Y1_
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] t = { 4, 2, 3, 7, 1, 5, 6 };
            DrzewoBST<int> d0 = CreateTreeFromArray(t);
            Console.ReadLine();
            d0.ShowInOrder();
            Console.WriteLine("Skoro inorder to posortowana tablica, ");
            List<int> list = new List<int>();
            foreach (var VARIABLE in t)
            {
                list.Add(VARIABLE);
            }
            list.Sort();
            int a = 3;
            int b = 6; // tu liczymy ile elementow znajduje sie w przedziale [a,b] Dokończyć samemu

            Console.ReadKey();
        }
        public static DrzewoBST<T> CreateTreeFromArray<T>(T[] array) where T : IComparable<T>
        {
            DrzewoBST<T> tree = new DrzewoBST<T>();
            foreach (T item in array)
            {
                tree.Insert(item);
            }
            return tree;
        }
    }

    class DrzewoBST<T> where T : IComparable<T>
    {
        class Node
        {
            public T value;
            public Node left;
            public Node right;

            public Node(T value)
            {
                this.value = value;
            }
        }

        Node root;

        public DrzewoBST()
        {
            this.root = null;
        }

        // in-order
        public void ShowInOrder()
        {
            this.ShowInOrder(this.root);
        }
        private void ShowInOrder(Node node)
        {
            if (node == null) return;
            ShowInOrder(node.left);
            Console.Write(node.value + " ");
            ShowInOrder(node.right);
        }


        // Wstawianie rekurencyjne
        public void Insert(T value)
        {
            Node node = new Node(value);
            if (this.root == null)
            {
                this.root = node;
            }
            else
            {
                Insert(this.root, node);
            }
        }
        private void Insert(Node root, Node node)
        {
            if (root.value.CompareTo(node.value) > 0)
            {
                if (root.left == null)
                {
                    root.left = node;
                }
                else
                {
                    Insert(root.left, node);
                }
            }
            else
            {
                if (root.right == null)
                {
                    root.right = node;
                }
                else
                {
                    Insert(root.right, node);
                }
            }
        }
    }

}

/////

static void Main( string[] args )
{
	List<List<int>> graf = new List<List<int>>();
	graf.Add( new List<int> { 2, 5 } );         // graf[ 0 ] zawiera sasiadow wierzcholka 1
	graf.Add( new List<int> { 1, 3, 5 } );
	graf.Add( new List<int> { 2, 4 } );
	graf.Add( new List<int> { 3, 5, 6 } );
	graf.Add( new List<int> { 1, 2, 4 } );
	graf.Add( new List<int> { 4 } );

	// Zaczynajac od wierzcholka 3, znajdz dlugosc drog do reszty wierzcholkow
	int v = 3;
	List<int> s = SciezkiDFS( graf, v );

	for( int i = 0; i < s.Count; i++ )
	{
		Console.WriteLine( $"Droga od {v} do {i+1} wynosi: {s[i]}" );

	}

	Console.ReadKey();
}

static List<int> SciezkiDFS( List<List<int>> graf, int v )
{
	List<int> sciezki = new List<int>();

	int pierwszy;
	if( v != 1 ) pierwszy = 1;
	else pierwszy = 2;

	for( int i = pierwszy; i < graf.Count + 1; i++ )
	{
		sciezki.Add( DlugoscSciezkiDFS( graf, v, i ) );
	}

	return sciezki;
}

static int DlugoscSciezkiDFS( List<List<int>> graf, int p, int k )
{
	List<int> sciezka = new List<int>();
	Stack<int> stack = new Stack<int>();
	bool[] odwiedzone = new bool[ graf.Count ];

	int obecny = p;
	stack.Push( obecny );
	odwiedzone[ obecny - 1 ] = true;

	while( stack.Count > 0 )
	{
		obecny = stack.Pop();

		if( obecny == k ) return sciezka.Count;

		sciezka.Add( obecny );

		for( int i = graf[ obecny - 1 ].Count - 1; i >= 0; --i )
		{
			if( !odwiedzone[ graf[ obecny - 1 ][ i ] - 1 ] )
			{
				stack.Push( graf[ obecny - 1 ][ i ] );
				odwiedzone[ graf[ obecny - 1 ][ i ] - 1 ] = true;
			}
		}
	}

	return 0;
}