手柄君的小阁

个人私货聚集地

NYOJ 题目42 一笔画问题(Java)

本文最后更新于 2018 年 5 月 10 日,其中的内容可能有所发展或发生改变,敬请注意。

题目来自于 南阳理工学院ACM在线测评系统

时间限制:3000 ms | 内存限制:65535 KB
难度:4

描述
zyc从小就比较喜欢玩一些小游戏,其中就包括画一笔画,他想请你帮他写一个程序,判断一个图是否能够用一笔画下来。
规定,所有的边都只能画一次,不能重复画。

输入
第一行只有一个正整数N(N<=10)表示测试数据的组数。
每组测试数据的第一行有两个正整数P,Q(P<=1000,Q<=2000),分别表示这个画中有多少个顶点和多少条连线。(点的编号从1到P)
随后的Q行,每行有两个正整数A,B(0<A,B<P),表示编号为A和B的两点之间有连线。

输出
如果存在符合条件的连线,则输出"Yes",
如果不存在符合条件的连线,输出"No"。

样例输入

2
4 3
1 2
1 3
1 4
4 5
1 2
2 3
1 3
1 4
3 4

样例输出

No
Yes

来源
[张云聪]原创

解题思路
首先,由于前一阵子刚好学到过一笔画相关解题法,故想起来需满足欧拉定理
    如果图形可以一笔画,那么一定满足以下条件:1.图形是封闭联通的;2.图形中和奇数个数边相连的点只有0个或者2个
由于当时只想起了条件2,故写出以下错误答案代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
import java.util.Scanner;
 
public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int loops = in.nextInt();
		int P,Q;
		int T;
		for(int i = 0; i < loops; i++){
			P = in.nextInt();
			Q = in.nextInt();
			int[] points = new int[P];
			for(int j = 0; j < Q; j++){
				points[in.nextInt()-1]+=1;
				points[in.nextInt()-1]+=1;
			}
			T = 0;
			for(int j = 0; j < P; j++){
				T += points[j] % 2;
			}
			System.out.println(T==0|T==2 ? "yes" : "no");
		}
		in.close();
	}
}

提交到NYOJ,判错误,理由为答案错误,尝试修改,得到以下错误答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
import java.util.Scanner;
 
public class Main {
 
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int loops = in.nextInt();
		int[] set = new int[loops];
		int P,Q;
		int T;
		for(int i = 0; i < loops; i++){
			P = in.nextInt();
			Q = in.nextInt();
			int[] points = new int[P];
			for(int j = 0; j < Q; j++){
				points[in.nextInt() - 1]+=1;
				points[in.nextInt() - 1]+=1;
			}
			T = 0;
			for(int j = 0; j < P; j++){
				if (points[j] == 0) {
					T = 1;
					return;
				}
				T += points[j] % 2;
			}
			set[i] = T;
		}
		in.close();
		for (int i = 0; i < set.length; i++){
			System.out.println(set[i] == 0 || set[i] == 2 ? "Yes" : "No");
		}
	}
}

后百度搜索一笔画条件,发现忽视欧拉定理第一个条件,故重写算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
import java.util.Scanner;
 
public class Main {
 
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int loops = in.nextInt();//一共有多少组待判断的图形
		int[] set = new int[loops];//用于输出结果的数组
		int P,Q;
		int T;//用于输出的临时存储媒介
		for(int i = 0; i < loops; i++){
			P = in.nextInt();//点的数量
			Q = in.nextInt();//边的数量
			int[] points1 = new int[Q];//待输入的边的端点数组1
			int[] points2 = new int[Q];//待输入的边的端点数组2
			int[] points = new int[P];
			for(int j = 0; j < Q; j++){
				points1[j] = in.nextInt();
				points2[j] = in.nextInt();
			}
			int[] pointsIn = new int[P];//互相联通的端点-数组
			pointsIn[points1[0]-1] = points1[0];
			pointsIn[points2[0]-1] = points2[0];
			T = 0;
			//判断是否连通图形
			//非连贯性地写入已和已知联通端点相联通的端点
			for(int j = 1; j < Q; j++){
				if(inInt(pointsIn,points1[j])){
					pointsIn[points2[j]-1] = points2[j];
				} else if(inInt(pointsIn,points2[j])){
					pointsIn[points1[j]-1] = points1[j];
				}
			}
			for(int j = 0; j < P; j++){
				//如果有端点未被包含在已联通的点内,则说明该图形并不是封闭联通的
				if (pointsIn[j] == 0) T = 1;
			}
			//判断是否符合欧拉定理第二条
			for(int j = 0; j < Q; j++){
				points[points1[j]-1] += 1;
				points[points2[j]-1] += 1;
			}
			if (T==0) {for(int j = 0; j < P; j++){
					T += points[j] % 2;//计算奇数端点数量
				}
			}
			set[i] = T;//将该组结果写入数组,等待输出
		}
		in.close();
		for (int i = 0; i < set.length; i++){
			System.out.println(set[i] == 0 || set[i] == 2 ? "Yes" : "No");//输出结果
		}
	}
	//定义方法,用于判断某个数是否包含在某数组内
	private static boolean inInt(int[] array,int searchInt){
		for (int i=0;i<array.length;i++){
			if (array[i] == searchInt){
				return true;
			}
		}
		return false;
	}
}

得到Accepted结果,通过时间169,内存335
优化,预先定义数组,增加新的第11行,得到

11
		int[] points1,points2,points;

修改15、16、17行

15
16
17
			points1 = new int[Q];
			points2 = new int[Q];
			points = new int[P];

得到Accepted结果,通过时间112,内存335
之后多次负优化均无法达到以上速度,不过内存占用小一点点……
下面献丑献上最后一版负优化版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
import java.util.Scanner;
 
public class Main {
 
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int loops = in.nextInt();
		boolean[] set = new boolean[loops];
		int P,Q;
		int[] points1,points2,pointsIn,points;
		boolean bool;
		for(int i = 0; i < loops; i++){
			P = in.nextInt();
			Q = in.nextInt();
			points1 = new int[Q];
			points2 = new int[Q];
			for(int j = 0; j < Q; j++){
				points1[j] = in.nextInt();
				points2[j] = in.nextInt();
			}
			pointsIn = new int[P];
			points  = new int[P];
			pointsIn[points1[0]-1] = points1[0];
			pointsIn[points2[0]-1] = points2[0];
			set[i] = true;
			//判断是否连通图形
			for(int j = 1; j < Q; j++){
				bool = false;
				for (int k = 0; k < P ; k++){
						if (pointsIn[k] == points1[j]){
							bool = true;
							break;
						}
				}
				if(bool){
					pointsIn[points2[j]-1] = points2[j];
				} else {
					bool = false;
					for (int k = 0; k < P ; k++){
							if (pointsIn[k] == points2[j]){
								bool = true;
								break;
							}
					}
					if(bool){
						pointsIn[points1[j]-1] = points1[j];
					}
				}
			}
			for(int j = 0; j < P; j++){
				if (pointsIn[j] == 0) set[i] = false;
			}
			//判断是否符合欧拉定理第二项
			if (set[i]) {
				for(int j = 0; j < Q; j++){
					points[points1[j]-1] += 1;
					points[points2[j]-1] += 1;
				}
				for(int j = 0, k = 0; j < P; j++){
					k += points[j] % 2;
					set[i] = (k == 0 || k == 2 ? true : false);
				}
			}
		}
		in.close();
		for (int i = 0; i < set.length; i++){
			System.out.println(set[i] ? "Yes" : "No");
		}
	}
}

以上,学到了些什么呢?
    1.设计算法烧脑子
    2.设计算法烧脑子
    3.再见我去打OW去了

  1. Katyusha Katyusha说道:

    qwq日常膜拜dalao

  2. 头像 镜子说道:

    不是那种能造轮子的人(

    1. 头像 Handle说道:

      所以吾要加油学习造轮子嘛

来一发吐槽