hdvsyu's blog

PAT 1130. Infix Expression (25)

Posted on 2018-03-15 Edited on 2025-12-14 In PAT

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))

通过寻找根节点的下标来划分左右子树，递归打印

#include <iostream>
#include <string>

using namespace std;

struct Node {
    string data;
    int leftChildIndex, rightChildIndex;
};

struct Node *nodes;

int rootIndex(bool *index, int n) {
    for (int i = 1; i <= n; i++) {
        if (!index[i]) {
            return i;
        }
    }
    return -1;
}

void printTree(int rootIndex) {
    int left = nodes[rootIndex].leftChildIndex;
    if (left != -1) {
        if (nodes[left].leftChildIndex != -1) printf("(");
        printTree(nodes[rootIndex].leftChildIndex);
        if (nodes[left].leftChildIndex != -1) printf(")");
    }
    cout << nodes[rootIndex].data;
    int right = nodes[rootIndex].rightChildIndex;
    if (right != -1) {
        if (nodes[right].rightChildIndex != -1) printf("(");
        printTree(nodes[rootIndex].rightChildIndex);
        if (nodes[right].rightChildIndex != -1) printf(")");
    }
}

int main() {
    int n = 0;
    cin >> n;
    nodes = new struct Node[n + 1];
    bool *index = new bool[n + 1];
    for (int i = 1; i <= n; i++) {
        cin >> nodes[i].data >> nodes[i].leftChildIndex >> nodes[i].rightChildIndex;
        if (nodes[i].leftChildIndex != -1) index[nodes[i].leftChildIndex] = true;
        if (nodes[i].rightChildIndex != -1) index[nodes[i].rightChildIndex] = true;
    }
    int root = rootIndex(index, n);
    if (root == -1) {
        cout << "error";
    } else {
        printTree(root);
    }
    delete[] index;
    delete[] nodes;
    return 0;
}

PAT 1043. Is It a Binary Search Tree (25)

Posted on 2018-03-14 Edited on 2025-12-14 In PAT

A Binary Search Tree (BST) is recursively defined as a binary tree which has the following properties:

The left subtree of a node contains only nodes with keys less than the node’s key.
The right subtree of a node contains only nodes with keys greater than or equal to the node’s key.
Both the left and right subtrees must also be binary search trees.

If we swap the left and right subtrees of every node, then the resulting tree is called the Mirror Image of a BST. Now given a sequence of integer keys, you are supposed to tell if it is the preorder traversal sequence of a BST or the mirror image of a BST.

Input Specification:

Each input file contains one test case. For each case, the first line contains a positive integer N (<=1000). Then N integer keys are given in the next line. All the numbers in a line are separated by a space.

Output Specification:

For each test case, first print in a line “YES” if the sequence is the preorder traversal sequence of a BST or the mirror image of a BST, or “NO” if not. Then if the answer is “YES”, print in the next line the postorder traversal sequence of that tree. All the numbers in a line must be separated by a space, and there must be no extra space at the end of the line.

Sample Input 1:

7
8 6 5 7 10 8 11

Sample Output 1:

YES
5 7 6 8 11 10 8

Sample Input 2:

7
8 10 11 8 6 7 5

Sample Output 2:

YES
11 8 10 7 5 6 8

Sample Input 3:

7
8 6 8 5 10 9 11

Sample Output 3:

NO

给出的是前序序列，序列中的第一个点是树中的根。从根的下一个结点开始遍历，直到找到一个比根还要大的结点；再从树的尾部往前找到第一个比根小的结点。如果这两个结点的下标不是相差一的关系，就说明这个树不满足二叉搜索树的定义。同理，可以得到镜像的二叉树是否满足关系。

#include <cstdio>
#include <vector>

int *pre;

void getPost(std::vector<int> &post, int s, int e, bool mirror) {
    if (s > e) {
        return;
    }
    int i = s + 1, j = e;
    if (!mirror) {
        while (i <= e && pre[s] > pre[i]) i++;
        while (j > s && pre[s] <= pre[j]) j--;
    } else {
        while (i <= e && pre[s] <= pre[i]) i++;
        while (j > s && pre[s] > pre[j]) j--;
    }
    if (i - j != 1) return;
    getPost(post, s + 1, j, mirror);
    getPost(post, i, e, mirror);
    post.push_back(pre[s]);
}

int main() {
    int n = 0;
    scanf("%d", &n);
    pre = new int[n];
    for (int i = 0; i < n; i++) {
        scanf("%d", &pre[i]);
    }
    std::vector<int> post;
    getPost(post, 0, n - 1, false);
    if (post.size() != n) {
        post.clear();
        getPost(post, 0, n - 1, true);
    }
    if (post.size() == n) {
        printf("YES\n%d", post[0]);
        for (int i = 1; i < post.size(); i++) {
            printf(" %d", post[i]);
        }
    } else {
        printf("NO");
    }
    delete[] pre;
    return 0;
}

QuotePrintable编码原理

Posted on 2018-03-08 Edited on 2025-12-14 In Computer Network

QuotePrintable的编码规则如下：

所有可打印的ASCII字符（十进制33~~126，十六进制21~~7E）可以用ASCII来直接表示，除了=（十进制61，十六进制3D）
任何8bit的值都可以表示用3个字符表示：一个等号（=）和两个十六进制位（0-9或A-F）来表示。
tab键（十进制9，十六进制9）和space键（十进制32，十六进制20）如果出现在行末，则需要在前面加上等号；如果不出现在行末，就可以直接用ASCII表示。

【例】将01001100 10011101 00111001进行quoted-printable编码。

【解】题中给出的三组8bit二进制数转化成十六进制数是4C 9D 39，根据上面的规则可知，9D不是可打印的ASCII码，故需添加等号，所以得到L=9D9的编码，其中L的ASCII是4C，9D无法直接用ASCII表示，需要加等号即=9D，9的ASCII是39。

参考：https://en.wikipedia.org/wiki/Quoted-printable

PAT 1127. ZigZagging on a Tree (30)

Posted on 2018-03-05 Edited on 2025-12-14 In PAT

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

根据后续和中序来确定一棵树的算法前面已经写过好几次了，这里就不再复讲了。确定了树的结构，就可以知道层序遍历的结果了，我这里把每一层的节点都分开存储，偶数层逆序输出，奇数层正序输出。 ps：我感觉我这个方法比较暴力，如果你有更好的方法，不介意的话可以跟我交流下呀~~

#include <cstdio>
#include <vector>
#include <queue>

using namespace std;

vector<int> in, post;

struct tree {
    int val, level;
    struct tree *left, *right;
};

int findRootInInorder(int inl, int inr, int val) {
    for (int i = inl; i <= inr; i++) {
        if (in[i] == val) return i;
    }
    return -1;
}

struct tree *buildTree(int inl, int inr, int postRoot, struct tree *root, int level) {
    if (inl > inr) return NULL;
    if (root == NULL) root = new struct tree();
    int inRoot = findRootInInorder(inl, inr, post[postRoot]);
    root->val = post[postRoot];
    root->level = level;
    root->left = buildTree(inl, inRoot - 1, postRoot - inr + inRoot - 1, root->left, level + 1);
    root->right = buildTree(inRoot + 1, inr, postRoot - 1, root->right, level + 1);
    return root;
}

vector<vector<int> > getLevelOrder(struct tree *root) {
    vector<vector<int> > levelOrder(30);
    queue<struct tree *> q;
    q.push(root);
    while (!q.empty()) {
        struct tree *t = q.front();
        q.pop();
        levelOrder[t->level].push_back(t->val);
        if (t->left != NULL) q.push(t->left);
        if (t->right != NULL) q.push(t->right);
    }
    return levelOrder;
}

void printZigZag(vector<vector<int> > levelOrder) {
    printf("%d", levelOrder[0][0]);
    for (int i = 1; i < levelOrder.size(); i++) {
        if (i % 2 == 0) {
            for (int j = levelOrder[i].size() - 1; j >= 0; j--) {
                printf(" %d", levelOrder[i][j]);
            }
        } else {
            for (int j = 0; j < levelOrder[i].size(); j++) {
                printf(" %d", levelOrder[i][j]);
            }
        }
    }
}

int main() {
    int n = 0;
    scanf("%d", &n);
    in.resize(n);
    post.resize(n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &in[i]);
    }
    for (int i = 0; i < n; i++) {
        scanf("%d", &post[i]);
    }

    struct tree *root = buildTree(0, n - 1, n - 1, NULL, 0);
    vector<vector<int> > levelOrder = getLevelOrder(root);
    printZigZag(levelOrder);
    return 0;
}

PAT 1068. 万绿丛中一点红(20)

Posted on 2018-03-05 Edited on 2025-12-14 In 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

为了便于处理，将数组开大两个长度，这样就可以不用进行边界判定了，减少了代码的复杂度。isGreatThanTOL函数检测当前像素是否与周边8个像素点的差大于tol。在主函数中，用unique记录颜色出现的次数，我们只去判定那些独一无二的颜色，如果颜色既是独一无二的又是比周边的像素颜色差充分大的，那么这个点就是我们要考虑的了。

#include <cstdio>
#include <map>
#include <vector>
#include <cmath>

using namespace std;

vector<vector<int> > pic;

bool isGreatThanTOL(int a, int b, int tol) {
    if (fabs(pic[a][b] - pic[a - 1][b])     <= tol) return false;
    if (fabs(pic[a][b] - pic[a - 1][b + 1]) <= tol) return false;
    if (fabs(pic[a][b] - pic[a - 1][b - 1]) <= tol) return false;
    if (fabs(pic[a][b] - pic[a][b + 1])     <= tol) return false;
    if (fabs(pic[a][b] - pic[a][b - 1])     <= tol) return false;
    if (fabs(pic[a][b] - pic[a + 1][b + 1]) <= tol) return false;
    if (fabs(pic[a][b] - pic[a + 1][b])     <= tol) return false;
    if (fabs(pic[a][b] - pic[a + 1][b - 1]) <= tol) return false;
    return true;
}

int main() {
    int m = 0, n = 0, tol = 0;
    scanf("%d %d %d", &m, &n, &tol);
    
    pic.resize(n + 2);
    for (int i = 0; i < n + 2; i++) {
        pic[i].resize(m + 2);
    }
    
    map<int, int> unique;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            scanf("%d", &pic[i][j]);
            unique[pic[i][j]]++;
        }
    }
    
    int a = 0, b = 0, cnt = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (unique[pic[i][j]] == 1 && isGreatThanTOL(i, j, tol)) {
                cnt++;
                a = i;
                b = j;
            }
        }
    }
    
    if (cnt == 0) {
        printf("Not Exist\n");
    } else if (cnt == 1) {
        printf("(%d, %d): %d\n", b, a, pic[a][b]);
    } else {
        printf("Not Unique\n");
    }
    return 0;
}

PAT 1066. 图像过滤(15)

Posted on 2018-03-05 Edited on 2025-12-14 In PAT

图像过滤是把图像中不重要的像素都染成背景色，使得重要部分被凸显出来。现给定一幅黑白图像，要求你将灰度值位于某指定区间内的所有像素颜色都用一种指定的颜色替换。

输入格式：

输入在第一行给出一幅图像的分辨率，即两个正整数M和N（0 < M, N <= 500），另外是待过滤的灰度值区间端点A和B（0 <= A < B <= 255）、以及指定的替换灰度值。随后M行，每行给出N个像素点的灰度值，其间以空格分隔。所有灰度值都在[0, 255]区间内。

输出格式：

输出按要求过滤后的图像。即输出M行，每行N个像素灰度值，每个灰度值占3位（例如黑色要显示为000），其间以一个空格分隔。行首尾不得有多余空格。

输入样例：

3 5 100 150 0
3 189 254 101 119
150 233 151 99 100
88 123 149 0 255

输出样例：

003 189 254 000 000
000 233 151 099 000
088 000 000 000 255

判断每个点的值是否在需要替换的区间内，在区内间，则输出替换的值；不再区间内，则输出原来的值

#include <cstdio>

int main() {
    int m = 0, n = 0, a = 0, b = 0, val = 0;
    scanf("%d %d %d %d %d", &m, &n, &a, &b, &val);

    int **pic = new int *[m];
    for (int i = 0; i < m; i++) {
        pic[i] = new int[n];
    }

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &pic[i][j]);
        }
    }

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (j != 0) {
                printf(" ");
            }
            if (pic[i][j] >= a && pic[i][j] <= b) {
                printf("%03d", val);
            } else {
                printf("%03d", pic[i][j]);
            }
        }
        printf("\n");
    }
    return 0;
}

PAT 1067. 试密码(20)

Posted on 2018-03-05 Edited on 2025-12-14 In PAT

当你试图登录某个系统却忘了密码时，系统一般只会允许你尝试有限多次，当超出允许次数时，账号就会被锁死。本题就请你实现这个小功能。

输入格式：

输入在第一行给出一个密码（长度不超过20的、不包含空格、Tab、回车的非空字符串）和一个正整数N（<= 10），分别是正确的密码和系统允许尝试的次数。随后每行给出一个以回车结束的非空字符串，是用户尝试输入的密码。输入保证至少有一次尝试。当读到一行只有单个#字符时，输入结束，并且这一行不是用户的输入。 #### 输出格式：对用户的每个输入，如果是正确的密码且尝试次数不超过N，则在一行中输出“Welcome in”，并结束程序；如果是错误的，则在一行中按格式输出“Wrong password: 用户输入的错误密码”；当错误尝试达到N次时，再输出一行“Account locked”，并结束程序。 #### 输入样例1：

Correct%pw 3
correct%pw
Correct@PW
whatisthepassword!
Correct%pw
#

输出样例1：

Wrong password: correct%pw
Wrong password: Correct@PW
Wrong password: whatisthepassword!
Account locked

输入样例2：

cool@gplt 3
coolman@gplt
coollady@gplt
cool@gplt
try again
#

输出样例2：

Wrong password: coolman@gplt
Wrong password: coollady@gplt
Welcome in

模拟判断的过程

#include <iostream>
#include <string>

using namespace std;

int main() {
    string corretPassowrd;
    int cnt = 0;
    cin >> corretPassowrd >> cnt;
    getchar();

    while (true) {
        string attemp;
        getline(cin, attemp);
        if (attemp == "#") {
            break;
        }

        if (attemp == corretPassowrd) {
            cout << "Welcome in" << endl;
            break;
        } else {
            cnt--;

            cout << "Wrong password: " << attemp << endl;
            if (cnt == 0) {
                cout << "Account locked" << endl;
                break;
            }
        }
    }
    return 0;
}

PAT 1069. 微博转发抽奖(20)

Posted on 2018-03-05 Edited on 2025-12-14 In PAT

小明PAT考了满分，高兴之余决定发起微博转发抽奖活动，从转发的网友中按顺序每隔N个人就发出一个红包。请你编写程序帮助他确定中奖名单。

输入格式：

输入第一行给出三个正整数M（<= 1000）、N和S，分别是转发的总量、小明决定的中奖间隔、以及第一位中奖者的序号（编号从1开始）。随后M行，顺序给出转发微博的网友的昵称（不超过20个字符、不包含空格回车的非空字符串）。注意：可能有人转发多次，但不能中奖多次。所以如果处于当前中奖位置的网友已经中过奖，则跳过他顺次取下一位。

输出格式：

按照输入的顺序输出中奖名单，每个昵称占一行。如果没有人中奖，则输出“Keep going…”。

输入样例1：

9 3 2
Imgonnawin!
PickMe
PickMeMeMeee
LookHere
Imgonnawin!
TryAgainAgain
TryAgainAgain
Imgonnawin!
TryAgainAgain

输出样例1：

PickMe
Imgonnawin!
TryAgainAgain

输入样例2：

2 3 5
Imgonnawin!
PickMe

输出样例2：

Keep going…

用map来记录一个用户是否已经获过奖了。当s > m，不满足抽奖规则，输出Keep going…；s <= m时，先输出第一个中奖的人，后面中奖的人根据根据规则继续往下推。

#include <iostream>
#include <vector>
#include <string>
#include <map>

using namespace std;

int main() {
    int m = 0, n = 0, s = 0;
    cin >> m >> n >> s;
    vector<string> forward(m + 1);
    for (int i = 1; i <= m; i++) {
        string nickname;
        cin >> nickname;
        forward[i] = nickname;
    }

    if (s > m) {
        cout << "Keep going..." << endl;
    } else {
        map<string, bool> winner;
        cout << forward[s] << endl;
        winner[forward[s]] = true;
        int i = s;
        while (i < m) {
            int cnt = 0;
            while (i < m && cnt < n) {
                i++;
                if (!winner[forward[i]]) {
                    cnt++;
                }
            }
            if (n == cnt) {
                cout << forward[i] << endl;
                winner[forward[i]] = true;
            }
        }
    }
    return 0;
}

PAT 1070. 结绳(25)

Posted on 2018-03-05 Edited on 2025-12-14 In PAT

给定一段一段的绳子，你需要把它们串成一条绳。每次串连的时候，是把两段绳子对折，再如下图所示套接在一起。这样得到的绳子又被当成是另一段绳子，可以再次对折去跟另一段绳子串连。每次串连后，原来两段绳子的长度就会减半。

给定N段绳子的长度，你需要找出它们能串成的绳子的最大长度。

输入格式：

每个输入包含1个测试用例。每个测试用例第1行给出正整数N (2 <= N <= 104)；第2行给出N个正整数，即原始绳段的长度，数字间以空格分隔。所有整数都不超过104。

输出格式：

在一行中输出能够串成的绳子的最大长度。结果向下取整，即取为不超过最大长度的最近整数。

输入样例：

8
10 15 12 3 4 13 1 15

输出样例：

14

用贪心的思想来解，最长的绳子折叠的次数越少越好。这里用到了优先队列priority_queue，它保证每次插入到队列中的值都是按顺序排列的，因此我们可以尽可能的找到最短的两条线段，折成新的绳子，然后继续找两个最短的绳子做折叠，直到只剩下一条绳子。

#include <queue>
#include <cstdio>
#include <functional>
#include <vector>

using namespace std;

int main() {
    int n = 0;
    scanf("%d", &n);
    priority_queue<int, vector<int>, greater<int> > q;
    for (int i = 0; i < n; i++) {
        int temp = 0;
        scanf("%d", &temp);
        q.push(temp);
    }

    while (q.size() > 1) {
        int a = q.top();
        q.pop();
        int b = q.top();
        q.pop();

        q.push((a + b) / 2);
    }
    printf("%d", q.top());
}

PAT 1126. Eulerian Path (25)

Posted on 2018-03-05 Edited on 2025-12-14 In PAT

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

题目的大意是判断给出的图是欧拉图、欧拉路径还是其他。欧拉图即每个节点的度（入度和出度之和）都是偶数次的，不会出现奇数次的度的节点欧拉路径即存在仅有两个节点的度为奇数次，其他节点的度皆为偶数次的节点上述讨论欧拉图和欧拉路径的前提是这个图是连通的 isConnected使用广度优先搜索的策略进行搜索，从任意一个节点出发，做连续的广度优先搜索，如果不能遍历到所有的节点，就说明这个图不是连通的，即这个图即不是欧拉图也不是欧拉路径 isEulerian和isSemiEulerian都是通过对节点的度进行遍历，去统计奇数次节点的个数来得到结果的最后打印出节点的度和结果

#include <cstdio>
#include <queue>

using namespace std;

int **graph, *degree;

void createArray(int n) {
    graph = new int *[n];
    for (int i = 0; i < n; i++) {
        graph[i] = new int[n];
    }
    degree = new int[n];
}

void initializerArray(int n) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            graph[i][j] = 0;
        }
        degree[i] = 0;
    }
}

void printDegree(int n) {
    printf("%d", degree[0]);
    for (int i = 1; i < n; i++) {
        printf(" %d", degree[i]);
    }
    printf("\n");
}

bool isEulerian(int n) {
    for (int i = 0; i < n; i++) {
        if (degree[i] % 2 != 0) {
            return false;
        }
    }
    return true;
}

bool isSemiEulerian(int n) {
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        if (degree[i] % 2 != 0) {
            cnt++;
        }
    }
    return cnt == 2;
}

// bfs
bool isConnected(int n) {
    int *isVisited = new int[n];
    int pre = 0;
    queue<int> q;
    q.push(pre);
    isVisited[pre] = true;
    while (!q.empty()) {
        pre = q.front();
        q.pop();
        for (int i = 0; i < n; i++) {
            if (!isVisited[i] && graph[pre][i] == 1) {
                q.push(i);
                isVisited[i] = true;
            }
        }
    }
    for (int i = 0; i < n; i++) {
        if (!isVisited[i]) {
            return false;
        }
    }
    return true;
}

int main() {
    int n = 0, m = 0;
    scanf("%d %d", &n, &m);
    createArray(n);
    initializerArray(n);
    for (int i = 0; i < m; i++) {
        int a = 0, b = 0;
        scanf("%d %d", &a, &b);
        graph[a - 1][b - 1] = graph[b - 1][a - 1] = 1;
        degree[a - 1]++;
        degree[b - 1]++;
    }
    printDegree(n);

    if (isConnected(n)) {
        if (isEulerian(n)) {
            printf("Eulerian");
        } else if (isSemiEulerian(n)) {
            printf("Semi-Eulerian");
        } else {
            printf("Non-Eulerian");
        }
    } else {
        printf("Non-Eulerian");
    }
    return 0;
}