路径判断

给定一个有N个顶点和E条边的无向图，请判断给定的两个顶点之间是否有路径存在。 假设顶点从0到N−1编号。

输入格式:

输入第1行给出2个整数N(0<N≤10)和E，分别是图的顶点数和边数。

随后E行，每行给出一条边的两个端点。每行中的数字之间用1空格分隔。

最后一行给出两个顶点编号i，j（0≤i,j<N）,i和j之间用空格分隔。

输出格式:

如果i和j之间存在路径，则输出"There is a path between i and j."，

否则输出"There is no path between i and j."。

输入样例1:

7 6
0 1
2 3
1 4
0 2
1 3
5 6
0 3

输出样例1:

There is a path between 0 and 3.

输入样例2:

7 6
0 1
2 3
1 4
0 2
1 3
5 6
0 6

输出样例2:

There is no path between 0 and 6.

#include<iostream>
#include<algorithm>
#include<cstring>using namespace std;
const int N = 110;
int p[N];
int n,m;
int x,y;int find(int x)
{if(p[x]!=x) p[x]=find(p[x]);  //区间合并+路径压缩return p[x];
}int main()
{cin>>n>>m;for(int i=0;i<n;i++) p[i]=i;  //初始化for(int i=0;i<m;i++){int a,b;cin>>a>>b;p[find(a)]=find(b);}cin>>x>>y;if(find(x)==find(y)) printf("There is a path between %d and %d.\n",x,y);elseprintf("There is no path between %d and %d.\n",x,y);return 0;
}