using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using QuickGraph;
using QuickGraph.Algorithms.Observers;
using QuickGraph.Algorithms.ShortestPath;
using QuickGraph.Graphviz;

namespace Lab7Exc2
{
    public class Node
    {
        public int Value { get; set; }
        public Node Next { get; set; }

        public Node(int value)
        {
            Value = value;
            Next = null;
        }
    }

    public class Graph
    {
        public int NumVertices { get; set; }
        public Node[] AdjList { get; set; }
        public bool[] IsIsolated { get; set; }

        public Graph(int numVertices)
        {
            if (numVertices < 1)
            {
                throw new ArgumentException("Invalid number of vertices");
            }
            NumVertices = numVertices;
            AdjList = new Node[numVertices + 1];
            IsIsolated = new bool[numVertices + 1];
        }

        public void AddEdge(int src, int dest)
        {
            if (src < 1 || src > NumVertices || dest < 1 || dest > NumVertices)
            {
                throw new ArgumentException("Invalid vertex number");
            }
            var newNode = new Node(dest);
            if (AdjList[src] == null)
            {
                AdjList[src] = newNode;
            }
            else
            {
                newNode.Next = AdjList[src];
                AdjList[src] = newNode;
            }
            IsIsolated[src] = false;
            IsIsolated[dest] = false;
        }

        public void FindIsolatedVertices()
        {
            for (int i = 1; i <= NumVertices; i++)
            {
                if (AdjList[i] == null)
                {
                    IsIsolated[i] = true;
                }
            }
        }

        public static Graph SetGraphFromConsole(bool allowIsolated)
        {
            try
            {
                Console.Write("Enter the number of vertices: ");
                int numVertices = int.Parse(Console.ReadLine());
                var graph = new Graph(numVertices);

                if (numVertices == 1)
                {
                    Console.WriteLine("The graph contains only one vertex.");
                    return graph;
                }

                if (allowIsolated)
                {
                    Console.Write("Enter the isolated vertices (space-separated, or press enter to skip): ");
                    string[] isolatedVertices = Console.ReadLine().Split();
                    foreach (string s in isolatedVertices)
                    {
                        int isolated = int.Parse(s);
                        graph.IsIsolated[isolated] = true;
                    }
                }

                Console.WriteLine("Enter the adjacency list for each vertex:");
                for (int i = 1; i <= numVertices; i++)
                {
                    Console.Write(i + ": ");
                    string[] adjList = Console.ReadLine().Split();
                    foreach (string s in adjList)
                    {
                        int dest = int.Parse(s);
                        graph.AddEdge(i, dest);
                    }
                }
                return graph;
            }
            catch (Exception e)
            {
                Console.WriteLine("Error: " + e.Message);
                return null;
            }
        }

        public static Graph SetGraphFromFile(string fileName)
        {
            try
            {
                if (!File.Exists(fileName))
                {
                    Console.WriteLine("File not found");
                    return null;
                }
                using (StreamReader sr = new StreamReader(fileName))
                {
                    int numVertices = int.Parse(sr.ReadLine());
                    var graph = new Graph(numVertices);

                    if (numVertices == 1)
                    {
                        Console.WriteLine("The graph contains only one vertex.");
                        return graph;
                    }

                    string[] isolatedVertices = sr.ReadLine().Split();
                    foreach (string s in isolatedVertices)
                    {
                        int isolated = int.Parse(s);
                        graph.IsIsolated[isolated] = true;
                    }

                    for (int i = 1; i <= numVertices; i++)
                    {
                        string[] adjList = sr.ReadLine().Split();
                        foreach (string s in adjList)
                        {
                            int dest = int.Parse(s);
                            graph.AddEdge(i, dest);
                        }
                    }
                    return graph;
                }
            }
            catch (Exception e)
            {
                Console.WriteLine("Error: " + e.Message);
                return null;
            }
        }
        public void VisualizeVertexCover(int[] cover)
        {
            Console.WriteLine("Graph:");
            for (int i = 1; i <= NumVertices; i++)
            {
                Console.Write(i + ": ");
                var current = AdjList[i];
                while (current != null)
                {
                    Console.Write(current.Value + " ");
                    current = current.Next;
                }
                Console.WriteLine();
            }
            Console.WriteLine("Vertex cover:");
            for (int i = 1; i <= NumVertices; i++)
            {
                if (cover.Contains(i))
                {
                    Console.ForegroundColor = ConsoleColor.Green;
                }
                Console.Write(i + " ");
                Console.ResetColor();
            }
            Console.WriteLine();
        }

        public int[] FindVertexCover()
        {
            FindIsolatedVertices();
            bool[] visited = new bool[NumVertices + 1];
            int[] cover = new int[NumVertices];
            int coverSize = 0;
            for (int i = 1; i <= NumVertices; i++)
            {
                if (!visited[i] && !IsIsolated[i])
                {
                    visited[i] = true;
                    cover[coverSize++] = i;
                    var current = AdjList[i];
                    while (current != null)
                    {
                        visited[current.Value] = true;
                        current = current.Next;
                    }
                }
            }
            Array.Resize(ref cover, coverSize);
            return cover;
        }
    }

}