// LeetCode problem: https://leetcode.com/problems/friend-circles/

using System;

using System.Collections.Generic;

public class Program

{

    public static void Main()

    {

        // TODO: Create jagged matrix

    }

    // M is the provided friend matrix

    // We need to represet and log the connected components in the graph using BFS and DFS

    // why does this work? Because applying transitive property to this : a friend of b, b friend of c , c friend of d

    // a,b,c,d should fall into 1 friend circle, imagine a,b,c,d to be nodes of graph and they are connected by an edge if they 

    // are friends else not connected by an edge, so simply finding the total groups / connected components gives us the answer. 

    // In the matrix connections are demonstrated by being either above, below, left, or right

    public static int FindCircleNum(int[][] M)

    {

        List<bool> friendZoned = new List<bool>(new bool[M.Length]);    // array to track visited in DFS

        foreach(bool b in friendZoned)

        {b.Equals(false);}

        Stack<int> dfs = new Stack<int>();                              // stack to implement DFS

        int circles = 0;

        for(int i = 0; i < M.Length; i++)

        {

            if(!friendZoned[i])

            {

                circles++;  // person is not in friend circle so start new friend circle

                // DFS magic spell 1) pop top & mark as visited 2) get neighbors 3) push to stack 4) repeat 1-2-3 while stack is empty, steps somewhat interchangeable

                // 3) -- push to stack

                dfs.Push(i);

                // 4) repeat while stack empty

                while(dfs.Count != 0)

                {

                    // 1) pop top & mark as visited

                    int current = dfs.Peek(); dfs.Pop();    //pop

                    friendZoned[current] = true;            // mark as visited

                    // 2) get its unvisited neighbors

                    for(int j = 0 ; j < M[current].Length; j++)

                    {

                        if(!friendZoned[j] && M[current][j] == 1)

                        {dfs.Push(j);}

                    }                       

                }

            }

        }

        return circles;     

    }

}