7-14 两点间有路径吗？

对于给定的无向图以及图中的两个顶点，计算两个顶点所在的连通分量中的顶点数，并且判断这两个顶点之间是否有路径。

输入格式:

第一行是不超过20的正整数N，表示图有N个顶点，顶点的编号即0~N-1；

接下来N行，是N*N的邻接矩阵，矩阵的元素间用空格分隔；

最后一行是用空格隔开的两个顶点编号v和w

输出格式:

第一行输出v所在的连通分量的顶点数

第二行输出w所在的连通分量的顶点数

第三行，若v和w之间有路径，则输出Yes，否则输出No

注意：当v和w是同一个顶点时，认为v和w之间是有路径的。

输入样例:

对于这个图：

8
0 1 1 0 0 0 0 1
1 0 0 0 1 0 0 0
1 0 0 0 1 0 0 0
0 0 0 0 0 1 0 0
0 1 1 0 0 0 0 0
0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0
1 3

输出样例:

5
2
No

代码长度限制

16 KB

时间限制

400 ms

内存限制

64 MB

栈限制

8192 KB

#include <stdbool.h>
#include <stdio.h>

#define N 20

void dfs(int v, int n, bool visit[], int adj[N][N], int *count)
{
    visit[v] = true;
    (*count)++;
    for (int i = 0; i < n; i++)
    {
        if (adj[v][i] == 1 && !visit[i])
        {
            dfs(i, n, visit, adj, count);
        }
    }
}

bool Connected(int v, int w, int n, bool visit[], int adj[N][N])
{
    if (v == w)
        return true;
    visit[v] = true;
    for (int i = 0; i < n; i++)
    {
        if (adj[v][i] == 1 && (!visit[i] || i == w))
        {
            if (i == w || Connected(i, w, n, visit, adj))
            {
                return true;
            }
        }
    }
    return false;
}

int main()
{
    int n;
    scanf("%d", &n);

    int adj[N][N];
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            scanf("%d", &adj[i][j]);
        }
    }

    int v, w;
    scanf("%d %d", &v, &w);

    bool visit[N] = {false};
    int countV = 0;
    dfs(v, n, visit, adj, &countV);
    printf("%d\n", countV);

    for (int i = 0; i < n; i++)
    {
        visit[i] = false;
    }
    int countW = 0;
    dfs(w, n, visit, adj, &countW);
    printf("%d\n", countW);

    for (int i = 0; i < n; i++)
    {
        visit[i] = false;
    }
    bool connected = Connected(v, w, n, visit, adj);
    if (connected)
    {
        printf("Yes\n");
    }
    else
    {
        printf("No\n");
    }

    return 0;
}