#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

// 基于宽度优先搜索算法进行拓扑排序的算法
void topologic_sort_using_breadth_first_search_algorithm(vector<vector<int>>& g, const int n, vector<int>& indegrees) {

  priority_queue<int, vector<int>, greater<int>> pq; // minimum heap

  for (int u = 1; u <= n; ++u)
    if (!indegrees[u]) pq.emplace(u);

  while (not pq.empty()) {
    const int curr = pq.top(); pq.pop();
    cout << curr << ' ';
    for (const int nxt : g[curr])
      if (!--indegrees[nxt]) pq.emplace(nxt);
  }
}


int main(void) {
  int n, m;
  cin >> n >> m;

  vector<vector<int>> g(n + 1);
  vector<int> indegrees(n + 1, 0); // 入度表

  int u, v;
  while (m--) {
    cin >> u >> v;
    g[u].emplace_back(v);
    ++indegrees[v];
  }

  topologic_sort_using_breadth_first_search_algorithm(g, n, indegrees);
  return 0;
}

#include <stdio.h>
#include <stdlib.h>

int main(void) {
  int n;
  while (scanf("%d", &n) != EOF) {
    int i, j, nums[n];
    for (i = 0; i < n; ++i) scanf("%d", nums + i);

    int ans = 0;
    for (i = 0, j = 0; j < n; ++j) {
      if (j == n - 1 || *(nums + j) > *(nums + j + 1)) {
        ans = fmax(ans, *(nums + j) - *(nums + i));
        i = j + 1;
      }
    }
    printf("%d\n", ans);
  }
  return 0;
}

#include <stdio.h>
#include <stdlib.h>

typedef struct ListNode {
  int val;
  struct ListNode* next;
} ListNode;

ListNode* swap(ListNode* head) {
  // recursion exit condition
  if (!head || !head->next) return head;

  ListNode* new_head = head->next;
  head->next = swap(new_head->next);
  new_head->next = head;
  return new_head;
}

int main() {
  int n, val;
  scanf("%d", &n);

  ListNode dummy, *tail = &dummy;
  while (scanf("%d", &val) != EOF) {
    tail = tail->next = (ListNode*) malloc(sizeof(ListNode));
    tail->val = val;
    tail->next = NULL;
  }

  ListNode* head = swap(dummy.next);
  while (head) {
    printf("%d ", head->val);
    head = head->next;
  }

  return 0;
}

class Solution {
public:
  string expressionTree(TreeNode* root) {
    return dfs(root->left) + root->val + dfs(root->right);
  }

private:
  string dfs(TreeNode* root) {
    if (!root) return "";
    if (!root->left && !root->right)
      return root->val;
    string ans = "(";
    ans += dfs(root->left);
    ans += root->val;
    ans += dfs(root->right) + ")";
    return ans;
  }
};

#include <stdio.h>
#include <stdlib.h>

#define not !

typedef enum { OK = 1, ERROR = -1, OVERFLOW = -2 } Status;

typedef int KeyElemType;

typedef struct BSTNode {
  KeyElemType key;
  struct BSTNode* left;
  struct BSTNode* right;
} BSTNode, *BST;

BST insertIntoBST(BST root, KeyElemType key) {
  if (!root) {
    if (!(root = (BSTNode*) malloc(sizeof(BSTNode))))
      return NULL;
    root->key = key;
    root->left = root->right = NULL;
    return root;
  }
  if (key < root->key)
    root->left = insertIntoBST(root->left, key);
  else if (key > root->key) 
    root->right = insertIntoBST(root->right, key);

  return root;
}

BST deleteNodeInBST(BST root, KeyElemType key) {
  if (!root) return NULL;
  if (key < root->key) {
    root->left = deleteNodeInBST(root->left, key);
  } else if (key > root->key) {
    root->right = deleteNodeInBST(root->right, key);
  } else {
    BST new_root;
    if (!root->left) new_root = root->right;
    else if (!root->right) new_root = root->left;
    else {
      BST parent = root;
      BSTNode* smallest = root->right;
      while (smallest->left) {
        parent = smallest;
        smallest = smallest->left;
      }

      if (parent != root) { // 外科手术般的指针操作，要非常的小心，不然内存布局乱了
        parent->left = smallest->right;
        smallest->right = root->right;
      }
      smallest->left = root->left;
      new_root = smallest;
    }
    free(root);
    return new_root;
  }

  return root;
}
// ==================== 顺序栈存储结构表示与实现 ====================
typedef BSTNode* SElemType;

typedef struct {
  SElemType* base;
  SElemType* top;
  size_t capacity;
} SqStack;


Status InitStack(SqStack* S, int initialCapacity) {
  if (initialCapacity < 1) return ERROR;

  S->base = (SElemType*) malloc(initialCapacity * sizeof(SElemType));
  S->top = S->base;
  S->capacity = initialCapacity;
  return OK;
}

int StackEmpty(SqStack* S) {
  return S->top == S->base;
}

int StackFull(SqStack* S) {
  return S->top - S->base == S->capacity;
}

size_t StackLength(SqStack* S) {
  return S->top - S->base;
}

void __large_capacity(SqStack* S) {
  // 预留的顺序栈扩容扩展接口
}

Status Push(SqStack* S, SElemType e) {
  if (StackFull(S))
    __large_capacity(S);
 *S->top++ = e;
 return OK;   
}

Status Pop(SqStack* S, SElemType* e) {
  if (StackEmpty(S)) {
    puts("Pop ERROR: The stack is empty!");
    return ERROR;
  }
  *e = *--S->top;
  return OK;
}

Status DestroyStack(SqStack* S) {
  free((*S).base);
  (*S).top = NULL;
  return OK;
}
// ==================== 顺序栈存储结构表示与实现 ====================

KeyElemType successor(BST root, KeyElemType key) {
  SqStack S;
  InitStack(&S, 2000);

  BSTNode *p = root, *cur;
  while (not StackEmpty(&S) || p) {
    while (p) {
      Push(&S, p);
      p = p->left;
    }
    Pop(&S, &cur);
    if (cur->key > key)
      return DestroyStack(&S), cur->key;

    p = cur->right;
  }

  return DestroyStack(&S), -1;
}

KeyElemType pre_successor(BST root, KeyElemType key) {
  SqStack S;
  InitStack(&S, 2000);

  BSTNode *p = root, *cur, *prev;
  while (not StackEmpty(&S) || p) {
    while (p) {
      Push(&S, p);
      p = p->left;
    }
    Pop(&S, &cur);
    if (cur->key >= key)
      return DestroyStack(&S), prev->key;

    prev = cur;
    p = cur->right;
  }

  return DestroyStack(&S), prev->key;
}


int main(const int argc, const char* const argv[]) {

  BST root = NULL;

  int n, opt, key;
  fscanf(stdin, "%d", &n);
  while (n--) {
    fscanf(stdin, "%d %d", &opt, &key);
    switch (opt) {
      case 1:
        root = insertIntoBST(root, key);
        break;
      case 2:
        root = deleteNodeInBST(root, key);
        break;
      case 3:
        fprintf(stdout, "%d\n", pre_successor(root, key));
        break;
      case 4:
        fprintf(stdout, "%d\n", successor(root, key));
        break;
      default:
        fputs(stdout, "option wrong!!!");
        break;
    }
  }

  return 0;
}

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
  void rearrangedList(ListNode* head) {
    vector<ListNode*> v;
    for (auto p = head; p; p = p->next)
      v.emplace_back(p);

    for (int i = 0; i < v.size() / 2; ++i) {
      v[i]->next = v[v.size() - 1 - i];
      v[v.size() - 1 - i]->next = v[i + 1];
    }
    v[v.size() / 2]->next = nullptr;
  }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
  ListNode* filterList(ListNode* head) {
    unordered_set<int> seen;
    auto prev = head, cur = head;
    while (cur) {
      if (seen.count(abs(cur->val)))
        prev->next = cur->next;
      else {
        seen.emplace(abs(cur->val));
        prev = cur;
      }
      cur = cur->next;
    }
    return head;
  }
};

在树上做动态规化

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

void dfs(vector<vector<int>>& g, int curr, int (*dp)[2], vector<int>& h) {
  dp[curr][1] += h[curr];
  for (const int child : g[curr]) {
    dfs(g, child, dp, h);
    dp[curr][1] += dp[child][0];
    dp[curr][0] += max(dp[child][0], dp[child][1]);
  }
}

int main(void) {
  int n;
  cin >> n;
  vector<vector<int>> g(n + 1);
  vector<int> h(n + 1);
  vector<int> has_parent(n + 1); 

  int dp[n + 1][2];
  memset(dp, 0x0000, sizeof dp);
  for (int i = 1; i <= n; ++i)
    cin >> h[i];

  int child, parent;
  for (int i = 0; i < n - 1; ++i) {
    cin >> child >> parent;
    g[parent].emplace_back(child);
    has_parent[child] = 1;
  }

  int root_id = 1;
  while (has_parent[root_id]) ++root_id;

  dfs(g, root_id, dp, h);
  cout << max(dp[root_id][0], dp[root_id][1]);
  return 0;
}

breadth_first_search_algorithm

#include <iostream>
#include <vector>
#include <deque>

using namespace std;

int breadth_first_search_algorithm(vector<vector<int>>& g, vector<int>& seen, int start) {
  deque q{{start}};
  seen[start] = 1; // mark as seen

  int dist = 0;
  while (not q.empty()) {
    size_t s = q.size();
    while (s--) {
      const int curr = q.front(); q.pop_front();
      for (const int nei : g[curr]) {
        if (seen[nei]) continue;
        q.emplace_back(nei);
        seen[nei] = 1;
      }
    }
    ++dist;
  }

  return dist - 1;
}

int main(const int argc, const char** argv) {
  int n, m, u, v;
  cin >> n >> m;
  vector<vector<int>> g(n + 1);
  vector<int> seen(n + 1, 0);
  for (int i = 0; i < n - 1; ++i) {
    cin >> u >> v;
    g[u].emplace_back(v);
    g[v].emplace_back(u);
  }

  int distance = breadth_first_search_algorithm(g, seen, m);
  cout << distance;
  return 0;
}

#define pathSum(root) __pathSum(root, 0)

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
int __pathSum(struct TreeNode* root, int depth) {
  if (!root) return 0;
  if (!root->left && !root->right)
    return root->val * depth;
  return __pathSum(root->left, depth + 1) + 
         __pathSum(root->right, depth + 1);
}