c - 如何使用 c 找到 DFS 中的组件数量？

Question

好吧，我遍历了 DFS，但现在我找不到组件。有什么办法可以解决。

for (i=1;i<=n;i++){
    for (j=1;j<=n;j++){
        printf("Enter the number of array position a[%d][%d] = ",i,j);
        scanf("%d",&ar[i][j]);
    }
}
DFS(v);
printf("\n");

for (i=1;i<=n;i++){
    if(reach[i]==1){
        count++;
    }
}
printf("Number of Components: %d",count);
    return 0;
}

标签： c

Answer 1

这是该任务的算法：

Components = 0; 

For every vertex index i:
   if marks[i] == 0 then
      ++Components
      DFS(i)

DFS(v):
   marks[v] = Components
   for all vertices j adjacent to v:
      if marks[j] == 0:
         DFS(j)

组件存储了个数，components表示marks[n]顶点n所属的组件号。