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

顺便当作介绍最萌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
", (flag == 2 || flag == 0) ? "YES" : "NO");
69     }
70     return 0;
71 }

View Code

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

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

just follow your heart