@@ -0,0 +1,1754 @@
+/**%0A * There are N students in a class. Some of them are friends, while some are not. %0A * Their friendship is transitive in nature. %0A * For example, if A is a direct friend of B, and B is a direct friend of C, then A is an indirect friend of C. %0A * And we defined a friend circle is a group of students who are direct or indirect friends.%0A * Given a N*N matrix M representing the friend relationship between students in the class. %0A * If M%5Bi%5D%5Bj%5D = 1, then the ith and jth students are direct friends with each other, otherwise not. %0A * And you have to output the total number of friend circles among all the students.%0A */%0Apublic int findCircleNum(int%5B%5D%5B%5D friends) %7B%0A  /**%0A   * For every %601%60 seen, increment the count by 1 and then change all direct and indirect relationships to 0 %0A   * because they are all in the same friend group.%0A   * The runtime is N%5E2 and the space complexity is N where N is the number of friends.%0A   */%0A%0A  int count = 0;%0A  Stack%3CInteger%3E stack = new Stack%3CInteger%3E();%0A  int%5B%5D visited = new int%5Bfriends.length%5D;%0A%0A  for (int i = 0; i %3C friends.length; i ++) %7B%0A    for (int j = 0; j %3C friends%5Bi%5D.length; j ++) %7B%0A      if (friends%5Bi%5D%5Bj%5D == 1) %7B%0A        count ++;%0A        stack.clear();%0A        stack.push(i);%0A        stack.push(j);%0A        while (!stack.isEmpty()) %7B%0A          int index = stack.pop();%0A          // If out of bounds or if we have marked the entire row already.%0A          if (index %3C 0 %7C%7C index %3E= friends.length %7C%7C visited%5Bindex%5D == 1) continue;%0A          visited%5Bindex%5D = 1;%0A          for (int k = 0; k %3C friends%5Bindex%5D.length; k ++) %7B%0A            if (friends%5Bindex%5D%5Bk%5D == 1) %7B%0A              friends%5Bindex%5D%5Bk%5D = 0;%0A              stack.push(k);%0A            %7D%0A          %7D%0A        %7D%0A      %7D%0A    %7D%0A  %7D%0A%0A  return count;%0A%7D

Add friend circles