public class Solution {
private void dfs(int[,] M, int[] visited, int i)
{
for (int j = ; j < M.GetLength(); j++)
{
if (M[i, j] == && visited[j] == )
{
visited[j] = ;
dfs(M, visited, j);
}
}
}
public int FindCircleNum(int[,] M)
{
int[] visited = new int[M.GetLength()];
int count = ;
for (int i = ; i < M.GetLength(); i++)
{
if (visited[i] == )
{
dfs(M, visited, i);
count++;
}
}
return count;
}
}这是第一种方法，主要是使用dfs来实现。
下面是第二种方法，是同学用python写的，我翻译成了C#，这种思路是union find。
public class Solution {
public int FindCircleNum(int[,] M)
{
var N = M.GetLength();
var groups = N;
var leads = new int[N];
for (var i = ; i < N; i++)
{
leads[i] = i;
}
for (var i = ; i < N; i++)
{
for (var j = i + ; j < N; j++)
{
if (M[i, j] == )
{
var lead1 = find(i, leads);
var lead2 = find(j, leads);
if (lead1 != lead2)
{
leads[lead1] = lead2;
groups--;
}
}
}
}
return groups;
}
private int find(int x, int[] parents)
{
if (parents[x] == x)
{
return x;
}
else
{
return find(parents[x], parents);
}
}
}从耗时角度来看，第一种效率略高一些。