C# DFS Solutions (Beats 92%)


  • 0
    K

    For each person, go through its row and add all the friends to a set, and DFS on those friends as well. By adding each friend to a set, they won't be used again since they already belong to a friend circle.

    public class Solution {
        public int FindCircleNum(int[,] M) {
            HashSet<int> set = new HashSet<int>();
            int circles = 0;
            for(int i = 0; i < M.GetLength(0); i++){
                if(!set.Contains(i)){
                    set.Add(i);
                    Helper(M, i, set);
                    circles++;
                }
            }
            
            return circles;
        }
        
        private void Helper(int[,] m, int i, HashSet<int> set){
            
            for(int j = 0; j < m.GetLength(1); j++){
                if(m[i,j] == 0){
                    continue;
                }
                if(set.Contains(j)){
                    continue;
                }
                set.Add(j);
                Helper(m, j, set);
            }
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.