首页 > 代码库 > NOJ--1064--用STL来实现半欧拉图的判断

NOJ--1064--用STL来实现半欧拉图的判断

2024-07-05 23:31:34   224人阅读

顺便当作介绍 最萌Oj---nbut

这应该算我的第一篇 写题目 主要好累 不想做新题目 而且这题也是蛮有价值的

   戳我      

好吧  个人还是更喜欢苹果 对棒子的产品无爱 ----话外音

题目大意：就是每一行 给你一条线段的2个点 它的2个端点由4个数字 即x y  x1 y1来表示

一共给你N行 我们就来判断下能不能用一笔画完成

它相比于以往 我遇见过的欧拉问题  只是麻烦在 需要用一个结构体来存储点的坐标  这也应该是这题的难点了

起初 我想用一个hash映射来完成 这样就会省事很多 ..... but fail

就简单的说下思路  就是随机选择一个点开始遍历与它相邻的点 如果未被访问过 就再以这个点为始点遍历与它相邻的顶点 直到所有可以遍历到的顶点 都访问为止

然后 我们判断下 我们dfs遍历到的顶点是否与所有的顶点个数相同 或者 所有顶点个数是否都被标记过   嗯  这是2种不同的实现 但是相同的思想 都是为了判断连通性

本题 我采用了前者最后  我通过奇度顶点的个数来判断 0个-欧拉图  2个--半欧拉图

 1 #include <iostream>
 2 #include <vector>
 3 #include <algorithm>
 4 #include <map>
 5 #include <set>
 6 using namespace std;
 7 
 8 struct point 
 9 {
10     int x, y;
11     point(int a, int b) 
12     {
13         x = a;
14         y = b;
15     }
16     bool operator<(const point& other) const 
17     {
18         return x < other.x || x == other.x && y < other.y;
19     }
20 };
21 
22 void eular(const point& now, set<point>& vis, map<point, vector<point> >& m)
23 {
24     vis.insert(now);
25     vector<point>::iterator it;
26     for (it = m[now].begin(); it != m[now].end(); it++)
27     {
28         if (vis.find(*it)==vis.end())
29         {
30             eular(*it, vis, m);
31         }
32     }
33 }
34 
35 int main()
36 {
37     int flag;
38     int a, b, c, d;
39     int n, i;
40     while (scanf("%d", &n)==1)
41     {
42         point p(0, 0), q(0, 0);
43         map<point, vector<point> > m;
44         for (i = 0; i<n; i++)
45         {
46             scanf("%d %d %d %d", &a, &b, &c, &d);
47             p = point(a, b);
48             q = point(c, d);
49             m[p].push_back(q);
50             m[q].push_back(p);
51         }
52         set<point> vis;
53         eular(p, vis, m);
54         flag = 0;
55         if (vis.size() != m.size()) 
56         {
57             flag = 10;
58         } else 
59         {
60             for (map<point, vector<point> > ::iterator it = m.begin(); it != m.end(); it++)
61              {
62                 if (it->second.size() % 2 != 0)
63                 {
64                     flag++;
65                 }
66             }
67         }
68         printf("%s\n", (flag == 2 || flag == 0) ? "YES" : "NO");
69     }
70     return 0;
71 }
View Code

其实 这里还有很多细节 类似于map使用iterator遍历 必须 自定义<运算符   而且由于map的key值是不能被改变的 所以必须用const

以上 就是某个大神唯一告诉我的了....

 

 

 

 

 

 

 

 

 

 


联系
我们