Java(javac 1.8) 解法, 执行用时: 58ms, 内存消耗: 14968K, 提交时间: 2017-12-10 13:50:50

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int t = in.nextInt();
		while (t-- > 0) {
			int n = in.nextInt();
			int m = in.nextInt();
			int x = in.nextInt();
			int y = in.nextInt();
			boolean[] nmap = new boolean[n + 1];
			boolean[][] map = new boolean[n + 1][n + 1];
			for (int i = 0; i < m; i++) {
				int xi = in.nextInt();
				int yi = in.nextInt();
				map[xi][yi] = true;
			}
			System.out.println(search(map, nmap, x, y) ? "Yes" : "No");
		}
	}

	static boolean search(boolean[][] map, boolean[] nmap, int last, int dest) {
		nmap[last] = true;
		if (last == dest)
			return true;

		boolean[] row = map[last];
		for (int j = 1; j < row.length; j++) {
			if (row[j] && !nmap[j])
				if (search(map, nmap, j, dest))
					return true;
		}
		for (int i = 1; i < nmap.length; i++) {
			if (map[i][last] && !nmap[i])
				if (search(map, nmap, i, dest))
					return true;
		}

		return false;
	}
}

C++14(g++5.4) 解法, 执行用时: 3ms, 内存消耗: 480K, 提交时间: 2020-05-09 21:56:56

#include <iostream>
//#include <cstring>
//#include <iomanip>
//#include <cmath>
//#include <string>
//#include <sstream>
//#include <algorithm>
//#include<set>
//#include<map>
//#include<unordered_map>
//#include <vector>
//#include <deque>
//#include <queue>
//#include<stack>
//# include<numeric>
//# include<bitset>
using namespace std;
const int maxn = 102;
int fa[maxn];

int find(int x)
{
	int y = x;
	int a;
	while (x != fa[x])
		x = fa[x];

	while (y != x)
	{
		a = fa[y];
		fa[y] = x;
		y = a;
	}
	return x;
}

void add(int x, int y)
{
	int a = find(x);
	int b = find(y);
	fa[a] = b;
}

int main()
{
	int t,n, m, x, y,a,b;
	cin >> t;

	while (t--)
	{
		cin >> n >> m >> x >> y;
		for (int i = 0; i <= n; i++)
			fa[i] = i;

		while (m--)
		{
			cin >> a >> b;
			add(a, b);
		}
		if (find(x) == find(y))
			cout << "Yes" << endl;
		else
			cout << "No" << endl;
	}

	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 5ms, 内存消耗: 464K, 提交时间: 2020-04-20 18:25:55

#include <cstdio>
using namespace std;
const int N = 105;
int fa[N];
int find(int x){
	return fa[x]==x?x:fa[x]=find(fa[x]);
}
void merge(int x,int y){
	int fx = find(x),fy = find(y);
	if(fx!=fy) fa[fx] = fy;
}
int n,m,x,y;
int main(){
	int t;scanf("%d",&t);
	while(t--){
		scanf("%d%d%d%d",&n,&m,&x,&y);
		for(int i = 1;i <= n;i++) fa[i] = i;
		while(m--){
			int u,v;scanf("%d%d",&u,&v);
			merge(u,v);
		}
		if(find(x)==find(y)) puts("Yes");
		else puts("No");
	}
	return 0;
}