63646566676869707172737475767778798081828384858687888990
using System;
using System.Collections.Generic;

public class Program
{
    public class Solution
    {
        /* Function to perform DFS traversal and 
        color the nodes with alternate colors*/
        private bool dfs(int node, int col, int[] color, List<int>[] adj)
        {
            // Color the current node
            color[node] = col;

            // Traverse adjacent nodes
            foreach (int it in adj[node])
            {
                // if uncoloured
                if (color[it] == -1)
                {
                    // Recursively color the nodes 
                    if (!dfs(it, 1 - col, color, adj))
                        return false;
                }
                // if previously coloured and have the same colour
                else if (color[it] == col)
                {
                    // Return false as it is not bipartite
                    return false;
                }
            }
            // Return true if all the nodes can 
            // be colored with alternate colors
            return true;
        }

        /* Function to check if the 
        given graph is bipartite */
        public bool IsBipartite(int V, List<int>[] adj)
        {
            // To store the color of nodes, where 
            // each node is uncolored initially
            int[] color = new int[V];
            Array.Fill(color, -1);

            // Start Traversal of connected components
            for (int i = 0; i < V; i++)
            {
                // if a node is not colored, 
                // a new component is found
                if (color[i] == -1)
                {
                    // Start DFS traversal 
                    // and color each node
                    if (!dfs(i, 0, color, adj))
                    {
                        // Return false if component 
                        // is found not to be bipartite
                        return false;
                    }
                }
            }
            // Return true if each 
            // component is bipartite
            return true;
        }
    }

    public static void Main(string[] args)
    {
        int V = 4;
        List<int>[] adj = new List<int>[V];
        adj[0] = new List<int> { 1, 3 };
        adj[1] = new List<int> { 0, 2 };
        adj[2] = new List<int> { 1, 3 };
        adj[3] = new List<int> { 0, 2 };

        // Creating an instance of Solution class
        Solution sol = new Solution();

        // Function call to check if the given graph is bipartite
        bool ans = sol.IsBipartite(V, adj);

        // Output
        if (ans)
            Console.WriteLine("The given graph is a bipartite graph.");
        else
            Console.WriteLine("The given graph is not a bipartite graph.");
    }
}
12345678910111213141516171819202122232425262728293031323334353637383940414243