Code – 第115页

《黑客与画家》读书笔记

2017-03-17 15:33:36

这时，“黑客”这个词不仅是第一流能力的象征，还包含着求解问题过程中产生的精神愉悦或享受。也就是说，从一开始，黑客就是有精神追求的。自由软件基金会创始人理查德·斯托尔曼说：“出于兴趣而解决某个难题，不管它有没有用，这就是黑客。”

2017-03-17 15:33:52

根据理查德·斯托尔曼的说法，黑客行为必须包含三个特点：好玩、高智商、探索精神。

2017-03-17 15:37:34

为了澄清“黑客”这个概念，他们提出只有传统意义上的黑客才能被称为hacker，而那些恶意入侵计算机系统的人应该被称为cracker（入侵者）。这个观点已经在程序员社区中得到普通认同。

2017-03-17 15:39:07

Hackers and Painters这个书名就是在提示应该把黑客与画家当作同一种人看待。和画家一样，黑客只是怀有一门特殊手艺、有创造天赋的普通人。这个书名还有另一层含义，即编程是一种艺术创作，黑客就是艺术家，开发软件与画家作画、雕塑家雕刻、建筑师设计房屋并没有本质不同。

2017-03-17 16:34:59

在一个人产生良知之前，折磨就是一种娱乐。

2017-03-17 16:35:48

但是我认为，孩子们欺负书呆子的主要原因也与追求“受欢迎”的心理有关。怎样才能让自己更受欢迎？个人魅力只是很小的一方面，你应该更多地考虑如何结盟。秘诀就是不停地设法使自己与其他受欢迎的人变得关系更密切。没有什么比一个共同的敌人更能使得人们团结起来了。

2017-03-17 16:37:55

如果说其中还有一丝安慰，那就是书呆子不妨记住，这种虐待不是针对个人的。一群孩子成群结伙地欺负你，那并不是因为你做错了什么，而是因为这一伙人需要找一件事情一起干，这就好像一群人成群结伙地去打猎一样。他们实际上并不恨你，他们只是需要一个共同的目标。

2017-03-19 15:55:51

我认为，真实世界的关键并非在于它是由成年人组成的，而在于它的庞大规模使得你做的每件事都能产生真正意义上的效果。学校、监狱、上流社会的女士午餐会，都做不到这一点。这些场合的成员都好像关在封闭的泡沫之中，所作所为只对泡沫内部有影响，对外部没有影响。那么很自然地，这些场合就会产生野蛮的做法。因为它们不具备实际功能，所以也就无所谓采用的形式^。

2017-03-19 15:56:50

「约翰·纳什（John Nash，1928—），美国著名数学家，因其对博弈论的突出贡献而获得1994年的诺贝尔经济学奖。纳什从小性格孤僻，不合群，读大学期间以行为古怪而闻名，30岁时就患上了严重的精神分裂症。电影《美丽心灵》讲述的就是他的故事。——译者注」

2017-03-19 15:57:41

因为我在这个世界中过得并不好，我觉得一定是自己什么地方做错了。我没有意识到，作为书呆子，我不适应周围环境，某种程度上正说明我领先了一步。书呆子已经在思考的东西，正是真实世界看重的东西。他们与别人不一样，不把所有时间用来玩一种耗尽全力但又亳无意义的游戏。

2017-03-19 16:34:07

对于书呆子来说，意识到学校并非全部的人生，也是很重要的事情。学校是一个很奇怪的、人为设计出来的体系，一半像是无菌室，一半像是野蛮洪荒之地。它就像人生一样，里面无所不包，但又不是事物的真实样子。它只是一个暂时的过程，只要你向前看，你就能超越它，哪怕现在你还是身处其中。

2017-03-19 16:36:25

「在英语中，“建筑师”（architect）和“架构师”（architect）是同一个词，所以这里用的是双关语，意思是优秀程序员不仅负责建造，还负责架构。后一句中的“建筑学”（architecture）也是这种双关用法，同时指“架构学”（architecture）。一译者注」

2017-03-19 16:39:46

首先，科学研究必须具有原创性。写过博士论文的人都知道，确保自己正在开垦新领地的方法，就是去找那些没有人要的土地。

2017-03-19 16:41:05

那么，为什么大学和实验室还把论文数量作为考核黑客工作的指标呢？这种事情其实在日常生活中普遍存在，比如，我们使用简单的标准化测试考核学生的“学术能力倾向”（scholastic aptitude），再比如，我们使用代码的行数考核程序员的工作效率。这样的考核容易实施，而容易实施的考核总是首先被采用。

2017-03-20 14:41:40

我对待代码的认真程度远远超过我对待其他事情，如果我以这种态度对待日常生活的每件事，那么我就够资格找心理医生开处方药了。看到代码前面的缩进乱七八糟，或者看到丑陋的变量名，都会把我逼疯的。

2017-03-20 14:42:06

黑客就像画家，工作起来是有心理周期的。有时候，你有了一个令人兴奋的新项目，你会愿意为它一天工作16个小时。等过了这一阵，你又会觉得百无聊赖，对所有事情都提不起兴趣。

2017-03-20 15:42:58

这时你要明白，自由思考比畅所欲言更重要。如果你感到一定要跟那些人辩个明自，绝不咽下这口气，一定要把话说清楚，结果很可能是从此你再也无法自由理性地思考了。我认为这样傲不可取，更好的方法是在思想和言论之间划一条明确的界线。在心里无所不想，但是不一定要说出来。我就鼓励自己在心里默默思考那些最无法无天的想法。你的思想是一个地下组织，绝不要把那里发生的事情一股脑说给外人听。

2017-03-20 15:43:38

因为弥尔顿是一个喜欢争论、好打嘴仗的人，而当时罗马教廷的宗教裁判所非常强势，所以沃顿爵士才会这样建议他。需要记住的是，弥尔顿的时代与我们的时代并没有本质不同。每个时代都有自己的忌讳，如果你触犯它们，就算没有坐牢，至少也会为自己惹来麻烦，干扰了正常生活。

2017-03-20 15:44:39

所以，如果可能的话，你最好找一些信得过的知己，只与他们畅所欲言、无所不谈。这样不仅可以获得新观点，还可以用来选择朋友。能够一起谈论“异端邪说”并且不会因此气急败坏的人，就是你最应该认识的朋友。

2017-03-20 20:28:05

互联网应用程序能够同时被多人使用，所以非常适合团队协作性的工作。大多数用户现在还不了解软件协同办公，否则估计他们会强烈要求大部分应用程序都具备这个功能。举例来说，允许两个用户同时编辑一个文档是一项很有用的功能。

2017-03-20 22:30:38

投资者和分析家会问，你们对未来有何计划。真实的回答是，我们没有任何计划。我们有改进的想法，但是如果我们想到应该怎么改进，就已经把它实现了。接下来六个月我们要做什么？所有能想到的最佳改进。我不知道自己是否有胆量公开这么说，但这是实话。计划这个词，只是将构思束之高阁的另一种表达方式。只要想到好的构思，我们就立刻着手实现。

继续阅读《黑客与画家》读书笔记

PAT 1130. Infix Expression (25)-甲级

Given a syntax tree (binary), you are supposed to output the corresponding infix expression, with parentheses reflecting the precedences of the operators.

Input Specification:
Each input file contains one test case. For each case, the first line gives a positive integer N ( <= 20 ) which is the total number of nodes in the syntax tree. Then N lines follow, each gives the information of a node (the i-th line corresponds to the i-th node) in the format:
data left_child right_child
where data is a string of no more than 10 characters, left_child and right_child are the indices of this node’s left and right children, respectively. The nodes are indexed from 1 to N. The NULL link is represented by -1. The figures 1 and 2 correspond to the samples 1 and 2, respectively.

Output Specification:
For each case, print in a line the infix expression, with parentheses reflecting the precedences of the operators. Note that there must be no extra parentheses for the final expression, as is shown by the samples. There must be no space between any symbols.
Sample Input 1:
8
* 8 7
a -1 -1
* 4 1
+ 2 5
b -1 -1
d -1 -1
– -1 6
c -1 -1
Sample Output 1:
(a+b)*(c*(-d))
Sample Input 2:
8
2.35 -1 -1
* 6 1
– -1 4
% 7 8
+ 2 3
a -1 -1
str -1 -1
871 -1 -1
Sample Output 2:
(a*2.35)+(-(str%871))

题目大意：给一个二叉树，输出中缀表达式，且加上括号表示运算的优先级～
分析：首先根据所有孩子结点编号寻找1～n中没有出现过的编号标记为root，即树的根结点～然后进行从root结点开始dfs～dfs递归拼接 “(” + 左子树 + 根 + 右子树 + “)”
递归有四种情况（有效的只有三种）：
1. 左右子树都空返回 “(” + 根 + “)”
2. 左空右不空返回 “(” + 根 + 右子树 + “)”
3. 左不空右空这种情况不存在
4. 左右都不空返回 “(” + 左子树 + 根 + 右子树 + “)”
最后递归返回的ans，最外层可能会被括号包起来，也可能不被包起来。要判断一下，如果被包起来，把最外层括号去掉即可～

#include <iostream>
using namespace std;
struct node {
    string data;
    int l, r;
}a[100];
string dfs(int root) {
    if(a[root].l == -1 && a[root].r == -1) return a[root].data;
    if(a[root].l == -1 && a[root].r != -1)  return "(" +  a[root].data + dfs(a[root].r) + ")";
    if(a[root].l != -1 && a[root].r != -1) return "(" +  dfs(a[root].l) + a[root].data + dfs(a[root].r) + ")";
}
int main() {
    int have[100] = {0}, n, root = 1;
    cin >> n;
    for(int i  = 1; i <= n; i++) {
        cin >> a[i].data >> a[i].l >> a[i].r;
        if(a[i].l != -1) have[a[i].l] = 1;
        if(a[i].r != -1) have[a[i].r] = 1;
    }
    while(have[root] == 1) root++;
    string ans = dfs(root);
    if(ans[0] == '(') ans = ans.substr(1,ans.size()-2);
    cout << ans;
    return 0;
}

#include <iostream>

using namespace std;

struct node {

string data;

int l, r;

}a[100];

string dfs(int root) {

if(a[root].l == -1 && a[root].r == -1) return a[root].data;

if(a[root].l == -1 && a[root].r != -1) return "(" + a[root].data + dfs(a[root].r) + ")";

if(a[root].l != -1 && a[root].r != -1) return "(" + dfs(a[root].l) + a[root].data + dfs(a[root].r) + ")";

}

int main() {

int have[100] = {0}, n, root = 1;

cin >> n;

for(int i = 1; i <= n; i++) {

cin >> a[i].data >> a[i].l >> a[i].r;

if(a[i].l != -1) have[a[i].l] = 1;

if(a[i].r != -1) have[a[i].r] = 1;

}

while(have[root] == 1) root++;

string ans = dfs(root);

if(ans[0] == '(') ans = ans.substr(1,ans.size()-2);

cout << ans;

return 0;

}

PAT 1128. N Queens Puzzle (20)-甲级

The “eight queens puzzle” is the problem of placing eight chess queens on an 8×8 chessboard so that no two queens threaten each other. Thus, a solution requires that no two queens share the same row, column, or diagonal. The eight queens puzzle is an example of the more general N queens problem of placing N non-attacking queens on an N×N chessboard. (From Wikipedia – “Eight queens puzzle”.)

Here you are NOT asked to solve the puzzles. Instead, you are supposed to judge whether or not a given configuration of the chessboard is a solution. To simplify the representation of a chessboard, let us assume that no two queens will be placed in the same column. Then a configuration can be represented by a simple integer sequence (Q1, Q2, …, QN), where Qi is the row number of the queen in the i-th column. For example, Figure 1 can be represented by (4, 6, 8, 2, 7, 1, 3, 5) and it is indeed a solution to the 8 queens puzzle; while Figure 2 can be represented by (4, 6, 7, 2, 8, 1, 9, 5, 3) and is NOT a 9 queens’ solution.

Input Specification:

Each input file contains several test cases. The first line gives an integer K (1 < K <= 200). Then K lines follow, each gives a configuration in the format “N Q1 Q2 … QN”, where 4 <= N <= 1000 and it is guaranteed that 1 <= Qi <= N for all i=1, …, N. The numbers are separated by spaces.

Output Specification:

For each configuration, if it is a solution to the N queens problem, print “YES” in a line; or “NO” if not.

Sample Input:
4
8 4 6 8 2 7 1 3 5
9 4 6 7 2 8 1 9 5 3
6 1 5 2 6 4 3
5 1 3 5 2 4
Sample Output:
YES
NO
NO
YES

题目大意：给出一个皇后图，以这样的方式给出：一个数组包含n个数字，每个数字表示该列的皇后所在的行数～判断给出的皇后图是否满足不会互相攻击（任意两个皇后都要不在同一行或者同一列，且不在斜对角线上～）
分析：用v[n]存储一张图给出的数字～对于第j个数字，判断前0～j-1个数字中是否有在同一行的（v[j] == v[t]）和在斜对角线上的（abs(v[j]-v[t]) == abs(j-t)）【因为已经告诉肯定不在同一列了，所以不需要判断是否在同一列啦～】如果发现了不满足的情况，就将result由true标记为false～最后根据result是true还是false输出对应的YES还是NO即可～

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
int main() {
    int k, n;
    cin >> k;
    for (int i = 0; i < k; i++) {
        cin >> n;
        vector<int> v(n);
        bool result = true;
        for (int j = 0; j < n; j++) {
            cin >> v[j];
            for (int t = 0; t < j; t++) {
                if (v[j] == v[t] || abs(v[j]-v[t]) == abs(j-t)) {
                    result = false;
                    break;
                }
            }
        }
        cout << (result == true ? "YES\n" : "NO\n");
    }
    return 0;
}

#include <iostream>

#include <vector>

#include <cmath>

using namespace std;

int main() {

int k, n;

cin >> k;

for (int i = 0; i < k; i++) {

cin >> n;

vector<int> v(n);

bool result = true;

for (int j = 0; j < n; j++) {

cin >> v[j];

for (int t = 0; t < j; t++) {

if (v[j] == v[t] || abs(v[j]-v[t]) == abs(j-t)) {

result = false;

break;

}

cout << (result == true ? "YES\n" : "NO\n");

}

return 0;

}

PAT 1127. ZigZagging on a Tree (30)-甲级

Suppose that all the keys in a binary tree are distinct positive integers. A unique binary tree can be determined by a given pair of postorder and inorder traversal sequences. And it is a simple standard routine to print the numbers in level-order. However, if you think the problem is too simple, then you are too naive. This time you are supposed to print the numbers in “zigzagging order” — that is, starting from the root, print the numbers level-by-level, alternating between left to right and right to left. For example, for the following tree you must output: 1 11 5 8 17 12 20 15.

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N (<= 30), the total number of nodes in the binary tree. The second line gives the inorder sequence and the third line gives the postorder sequence. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print the zigzagging sequence of the tree in a line. All the numbers in a line must be separated by exactly one space, and there must be no extra space at the end of the line.

Sample Input:
8
12 11 20 17 1 15 8 5
12 20 17 11 15 8 5 1
Sample Output:
1 11 5 8 17 12 20 15

题目大意：给出一个树的中序和后序遍历结果，求它的Z字型层序遍历，也就是偶数层从右往左，奇数层从左往右遍历～
分析：分为3步：1.根据中序和后序建树保存在tree二维数组中，比如：tree[i][0] = val表示post[i]的左孩子是post[val]，tree[i][1] = val表示post[i]的右孩子是post[val]～
2.进行广度优先搜索，将树从根结点开始所有结点层序遍历，保存在result二维数组中，比如：result[i]保存第i层所有结点的序列～
3.进行z字型输出，根据当前层号的奇偶性分别从左往右、从右往左遍历输出～

1. dfs：因为post(后序)是按照左、右、根的顺序遍历的，所以从右往左，最右边的肯定是根结点～所以postRight是当前子树的根结点的下标，将它的赋值给index，并继续dfs tree[index][0]和tree[index][1]～
根据post[postRight]的结点在in里面的下标位置i，可以得到i的左边是左子树，即inLeft 到 i – 1，右边是右子树：i + 1 到 inRight。而对于post来说，根据左子树的结点个数i – inLeft可以得到[postLeft, postLeft + (i – inLeft) – 1]是post中左子树的范围，[postLeft + (i – inLeft), postRight – 1]是post中右子树的范围～
2.广度优先搜索，采用队列q，q中保存的是node结点，node.index表示当前节点在post中的下标，node.depth表示当前结点在树中的层数～
3.当 i % 2 == 0的时候倒序输出，否则正序输出～

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
vector<int> in, post, result[35];
int n, tree[35][2], root;
struct node {
    int index, depth;
};
void dfs(int &index, int inLeft, int inRight, int postLeft, int postRight) {
    if (inLeft > inRight) return;
    index = postRight;
    int i = 0;
    while (in[i] != post[postRight]) i++;
    dfs(tree[index][0], inLeft, i - 1, postLeft, postLeft + (i - inLeft) - 1);
    dfs(tree[index][1], i + 1, inRight, postLeft + (i - inLeft), postRight - 1);
}
void bfs() {
    queue<node> q;
    q.push(node{root, 0});
    while (!q.empty()) {
        node temp = q.front();
        q.pop();
        result[temp.depth].push_back(post[temp.index]);
        if (tree[temp.index][0] != 0)
            q.push(node{tree[temp.index][0], temp.depth + 1});
        if (tree[temp.index][1] != 0)
            q.push(node{tree[temp.index][1], temp.depth + 1});
    }
}
int main() {
    cin >> n;
    in.resize(n + 1), post.resize(n + 1);
    for (int i = 1; i <= n; i++) cin >> in[i];
    for (int i = 1; i <= n; i++) cin >> post[i];
    dfs(root, 1, n, 1, n);
    bfs();
    printf("%d", result[0][0]);
    for (int i = 1; i < 35; i++) {
        if (i % 2 == 1) {
            for (int j = 0; j < result[i].size(); j++)
                printf(" %d", result[i][j]);
        } else {
            for (int j = result[i].size() - 1; j >= 0; j--)
                printf(" %d", result[i][j]);
        }
    }
    return 0;
}

#include <iostream>

#include <vector>

#include <queue>

using namespace std;

vector<int> in, post, result[35];

int n, tree[35][2], root;

struct node {

int index, depth;

};

void dfs(int &index, int inLeft, int inRight, int postLeft, int postRight) {

if (inLeft > inRight) return;

index = postRight;

int i = 0;

while (in[i] != post[postRight]) i++;

dfs(tree[index][0], inLeft, i - 1, postLeft, postLeft + (i - inLeft) - 1);

dfs(tree[index][1], i + 1, inRight, postLeft + (i - inLeft), postRight - 1);

}

void bfs() {

queue<node> q;

q.push(node{root, 0});

while (!q.empty()) {

node temp = q.front();

q.pop();

result[temp.depth].push_back(post[temp.index]);

if (tree[temp.index][0] != 0)

q.push(node{tree[temp.index][0], temp.depth + 1});

if (tree[temp.index][1] != 0)

q.push(node{tree[temp.index][1], temp.depth + 1});

}

int main() {

cin >> n;

in.resize(n + 1), post.resize(n + 1);

for (int i = 1; i <= n; i++) cin >> in[i];

for (int i = 1; i <= n; i++) cin >> post[i];

dfs(root, 1, n, 1, n);

bfs();

printf("%d", result[0][0]);

for (int i = 1; i < 35; i++) {

if (i % 2 == 1) {

for (int j = 0; j < result[i].size(); j++)

printf(" %d", result[i][j]);

} else {

for (int j = result[i].size() - 1; j >= 0; j--)

printf(" %d", result[i][j]);

}

return 0;

}

1068. 万绿丛中一点红(20)-PAT乙级真题

对于计算机而言，颜色不过是像素点对应的一个24位的数值。现给定一幅分辨率为MxN的画，要求你找出万绿丛中的一点红，即有独一无二颜色的那个像素点，并且该点的颜色与其周围8个相邻像素的颜色差充分大。

输入格式：

输入第一行给出三个正整数，分别是M和N（<= 1000），即图像的分辨率；以及TOL，是所求像素点与相邻点的颜色差阈值，色差超过TOL的点才被考虑。随后N行，每行给出M个像素的颜色值，范围在[0, 224)内。所有同行数字间用空格或TAB分开。

输出格式：

在一行中按照“(x, y): color”的格式输出所求像素点的位置以及颜色值，其中位置x和y分别是该像素在图像矩阵中的列、行编号（从1开始编号）。如果这样的点不唯一，则输出“Not Unique”；如果这样的点不存在，则输出“Not Exist”。

输入样例1：

8 6 200
0 0 0 0 0 0 0 0
65280 65280 65280 16711479 65280 65280 65280 65280
16711479 65280 65280 65280 16711680 65280 65280 65280
65280 65280 65280 65280 65280 65280 165280 165280
65280 65280 16777015 65280 65280 165280 65480 165280
16777215 16777215 16777215 16777215 16777215 16777215 16777215 16777215

输出样例1：
(5, 3): 16711680

输入样例2：
4 5 2
0 0 0 0
0 0 3 0
0 0 0 0
0 5 0 0
0 0 0 0

输出样例2：
Not Unique

输入样例3：
3 3 5
1 2 3
3 4 5
5 6 7

输出样例3：
Not Exist

分析：首先这个点必须是唯一的，所以用map标记如果不是唯一的点就不用考虑了～接着对于每个点，判断它的周围八个点与它的差值是否大于阈值，如果有一个点没有满足大于阈值就return false～最后记得输入的时候是列、行——m、n，输出的时候也是列、行坐标～

#include <iostream>
#include <vector>
#include <map>
using namespace std;
int m, n, tol;
vector<vector<int>> v;
int dir[8][2] = {{-1, -1}, {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}};
bool judge(int i, int j) {
    for (int k = 0; k < 8; k++) {
        int tx = i + dir[k][0];
        int ty = j + dir[k][1];
        if (tx >= 0 && tx < n && ty >= 0 && ty < m && v[i][j] - v[tx][ty] >= 0 - tol && v[i][j] - v[tx][ty] <= tol) return false;
    }
    return true;
}
int main() {
    int cnt = 0, x = 0, y = 0;
    scanf("%d%d%d", &m, &n, &tol);
    v.resize(n, vector<int>(m));
    map<int, int> mapp;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%d", &v[i][j]);
            mapp[v[i][j]]++;
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (mapp[v[i][j]] == 1 && judge(i, j) == true) {
                cnt++;
                x = i + 1;
                y = j + 1;
            }
        }
    }
    if (cnt == 1)
        printf("(%d, %d): %d", y, x, v[x-1][y-1]);
    else if (cnt == 0)
        printf("Not Exist");
    else
        printf("Not Unique");
    return 0;
}

#include <iostream>

#include <vector>

#include <map>

using namespace std;

int m, n, tol;

vector<vector<int>> v;

int dir[8][2] = {{-1, -1}, {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}};

bool judge(int i, int j) {

for (int k = 0; k < 8; k++) {

int tx = i + dir[k][0];

int ty = j + dir[k][1];

if (tx >= 0 && tx < n && ty >= 0 && ty < m && v[i][j] - v[tx][ty] >= 0 - tol && v[i][j] - v[tx][ty] <= tol) return false;

}

return true;

}

int main() {

int cnt = 0, x = 0, y = 0;

scanf("%d%d%d", &m, &n, &tol);

v.resize(n, vector<int>(m));

map<int, int> mapp;

for (int i = 0; i < n; i++) {

for (int j = 0; j < m; j++) {

scanf("%d", &v[i][j]);

mapp[v[i][j]]++;

}

for (int i = 0; i < n; i++) {

for (int j = 0; j < m; j++) {

if (mapp[v[i][j]] == 1 && judge(i, j) == true) {

cnt++;

x = i + 1;

y = j + 1;

}

if (cnt == 1)

printf("(%d, %d): %d", y, x, v[x-1][y-1]);

else if (cnt == 0)

printf("Not Exist");

else

printf("Not Unique");

return 0;

}

PAT 1126. Eulerian Path (25)-甲级

In graph theory, an Eulerian path is a path in a graph which visits every edge exactly once. Similarly, an Eulerian circuit is an Eulerian path which starts and ends on the same vertex. They were first discussed by Leonhard Euler while solving the famous Seven Bridges of Konigsberg problem in 1736. It has been proven that connected graphs with all vertices of even degree have an Eulerian circuit, and such graphs are called Eulerian. If there are exactly two vertices of odd degree, all Eulerian paths start at one of them and end at the other. A graph that has an Eulerian path but not an Eulerian circuit is called semi-Eulerian. (Cited from https://en.wikipedia.org/wiki/Eulerian_path)

Given an undirected graph, you are supposed to tell if it is Eulerian, semi-Eulerian, or non-Eulerian.

Input Specification:

Each input file contains one test case. Each case starts with a line containing 2 numbers N (<= 500), and M, which are the total number of vertices, and the number of edges, respectively. Then M lines follow, each describes an edge by giving the two ends of the edge (the vertices are numbered from 1 to N).

Output Specification:

For each test case, first print in a line the degrees of the vertices in ascending order of their indices. Then in the next line print your conclusion about the graph — either “Eulerian”, “Semi-Eulerian”, or “Non-Eulerian”. Note that all the numbers in the first line must be separated by exactly 1 space, and there must be no extra space at the beginning or the end of the line.

Sample Input 1:
7 12
5 7
1 2
1 3
2 3
2 4
3 4
5 2
7 6
6 3
4 5
6 4
5 6
Sample Output 1:
2 4 4 4 4 4 2
Eulerian
Sample Input 2:
6 10
1 2
1 3
2 3
2 4
3 4
5 2
6 3
4 5
6 4
5 6
Sample Output 2:
2 4 4 4 3 3
Semi-Eulerian
Sample Input 3:
5 8
1 2
2 5
5 4
4 1
1 3
3 2
3 4
5 3
Sample Output 3:
3 3 4 3 3
Non-Eulerian

题目大意：如果一个连通图的所有结点的度都是偶数，那么它就是Eulerian，如果除了两个结点的度是奇数其他都是偶数，那么它就是Semi-Eulerian，否则就是Non-Eulerian～
分析：用邻接表存储图，判断每个结点的度【也就是每个结点i的v[i].size()】是多少即可得到最终结果～注意：图必须是连通图，所以要用一个深搜判断一下连通性，从结点1开始深搜，如果最后发现统计的连通结点个数cnt != n说明是不是连通图，要输出Non-Eulerian～

#include <iostream>
#include <vector>
using namespace std;
vector<vector<int> > v;
vector<bool> visit;
int cnt = 0;
void dfs(int index) {
    visit[index] = true;
    cnt++;
    for (int i = 0; i < v[index].size(); i++)
        if (visit[v[index][i]] == false)
            dfs(v[index][i]);
}
int main() {
    int n, m, a, b, even = 0;
    scanf("%d%d", &n, &m);
    v.resize(n + 1);
    visit.resize(n + 1);
    for (int i = 0; i < m; i++) {
        scanf("%d%d", &a, &b);
        v[a].push_back(b);
        v[b].push_back(a);
    }
    for (int i = 1; i <= n; i++) {
        if (i != 1) printf(" ");
        printf("%d", v[i].size());
        if (v[i].size() % 2 == 0) even++;
    }
    printf("\n");
    dfs(1);
    if (even == n && cnt == n)
        printf("Eulerian");
    else if(even == n - 2 && cnt == n)
        printf("Semi-Eulerian");
    else
        printf("Non-Eulerian");
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

vector<vector<int> > v;

vector<bool> visit;

int cnt = 0;

void dfs(int index) {

visit[index] = true;

cnt++;

for (int i = 0; i < v[index].size(); i++)

if (visit[v[index][i]] == false)

dfs(v[index][i]);

}

int main() {

int n, m, a, b, even = 0;

scanf("%d%d", &n, &m);

v.resize(n + 1);

visit.resize(n + 1);

for (int i = 0; i < m; i++) {

scanf("%d%d", &a, &b);

v[a].push_back(b);

v[b].push_back(a);

}

for (int i = 1; i <= n; i++) {

if (i != 1) printf(" ");

printf("%d", v[i].size());

if (v[i].size() % 2 == 0) even++;

}

printf("\n");

dfs(1);

if (even == n && cnt == n)

printf("Eulerian");

else if(even == n - 2 && cnt == n)

printf("Semi-Eulerian");

else

printf("Non-Eulerian");

return 0;

}