6-2 两顶点之前有路径吗？

6-2 两顶点之前有路径吗？

6-2 两顶点之前有路径吗？ (20 分)

对于给定的无向图及两个图中的顶点，请实现一个函数，分别打印包含这两个顶点的连通分量中的顶点数，并判断这两个顶点之间是否有路径。

函数接口定义：
int hasPath(struct Graph *g, int v, int w);
其中v和w是顶点
图定义如下:

#define MaxVertexNum 20   
struct Graph{
    int v;    
    int Adj[MaxVertexNum][MaxVertexNum]; 
};

题目保证图至少有一个顶点
函数分别在第一行和第二行打印包含v和w的连通分量中顶点的数量。
如果 v和w之间有路径，函数返回1, 否则返回0.
提示:

你可以定义多个函数，也可以定义全局变量.
当v和w是同一个顶点时，认为v和w之间是有路径的。
裁判测试程序样例：

#include 
#include 
#define MaxVertexNum 20   
struct Graph{
    int v;  // amount of vertices
    int Adj[MaxVertexNum][MaxVertexNum]; 
};
int visited[MaxVertexNum]; 
struct Graph* CreateGraph(){
    int v;
    scanf("%d",&v);
    struct Graph* g;
    g = malloc(sizeof(struct Graph));
    if(!g) return NULL;
    g->v = v;
    for(int i=0; iAdj[i][j]));
    }
    return g;
}
int hasPath(struct Graph *g, int v, int w);
int main(){
    struct Graph* g;
    g = CreateGraph();
    int v,w;
    scanf("%d%d", &v, &w);
    printf("%sn", hasPath(g,v,w) ? "Yes" : "No");
    return 0;
}

输入样例：

对于此图及样例测试程序规定的输入格式：

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
结尾无空行
Sample Output：
5
2
No
结尾无空行

C(gcc)

int F = 0;
int hasPath(struct Graph* g, int v, int w)
{
    int q[1000];
    int l = 0, r = 0, t;
    visited[v] = 1;
    q[r++] = v;
    while (l < r)
    {
        t = q[l++]; 
        if (t == w) { F = 1; break; }
        for (int i = 0; i < g->v; i++)
        {
            if (g->Adj[t][i] && visited[i] == 0)
            {
                q[r++] = i; visited[i] = 1;
            }
        }
    }
    travel(g, v);
    travel(g, w);
    return F;
}
void travel(struct Graph* g, int v)// BFS统计连通分量顶点个数
{
    for (int i = 0; i < g->v; i++)visited[i] = 0;//清空搜索记录
    int q[1000];
    int l = 0, r = 0, c = 0, t;
    visited[v] = 1;
    q[r++] = v;
    while (l < r)
    {
        t = q[l++]; c++;
        for (int i = 0; i < g->v; i++)
        {
            if (g->Adj[t][i] && visited[i] == 0)
            {
                q[r++] = i; visited[i] = 1;
            }
        }
    }
    printf("%dn", c);
}