# Sprint 4 Module Project 2
## CS Friend Circles

"""
Understand

The examples given are good enough.

Plan
1. Translate the problem into graph terminology
- This is a typical adjacency matrix graph representation
- student = node
- matrix[i][j] = True if student i is friends with student j (edge)

2. Build your graph
- The graph is already built. It's an adjacency matrix

3. Traverse the graph
- For each student traverse their social circle
- Make sure to mark students previously visited so that you don't revisit the same social circle
- Count the number of social circles visited
- Any traversal will work

Runtime: O(number of nodes) we'll only visit each node/student once
Space: O(number of nodes) the size of our stack will not exceed the number of nodes
since we mark them as visited when we push onto the stack
"""

from collections import deque

def csFriendCircles(friendships):
    numSocialCircle = 0
    visited = set()
    for student in range(len(friendships)):
        if not student in visited:
            numSocialCircle += 1
            traverseSocialCircle(friendships, student, visited)
    return numSocialCircle

def traverseSocialCircle(graph, startingNode, visited):
    stack = deque()
    stack.append(startingNode)
    visited.add(startingNode)
    while len(stack) > 0:
        curr = stack.pop()
        for (node, edge) in enumerate(graph[curr]):
            if edge == 1 and not node in visited:
                visited.add(node)
                stack.append(node)