Short AC code (DFS)


  • 0
    M
    public class Solution
    {
        int circles = 0;
        public int FindCircleNum(int[,] M)
        {
            int m = M.GetLength(0);
            int n = M.GetLength(1);
    
            for (int i = 0; i < m; i++) 
                for (int j = 0; j < n; j++) 
                    if (M[i, j] == 1){circles++; DFS(M, m, n, i, j);}
    
            return circles;
        }
    
        private void DFS(int[,] M, int m, int n, int x, int y)  
        {
            if (x < 0 || x >= m || y < 0 || y >= m) return;
            M[x, y] = 0; M[y, x] = 0;
    
            for (int i = 0; i < n; i++)
            {
                if (M[x, i] == 1) { M[x, i] = 0; M[i, x] = 0; if (x != i) DFS(M, m, n, i, 0);}
            }
        }
    }
    

Log in to reply
 

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