#include <algorithm> #include <iostream> #include <set> #include <vector> using namespace std; class UnionFind { private: vector<int> f; vector<int> rank; public: UnionFind(int n): f(n+1,0), rank(n+1,0) { for (int i = 1; i <= n; i++) { f[i] = i; } } void merge(...

#include <algorithm> #include <iostream> #include <vector> using namespace std; const int N = 100+10; int f[N] = {0}; int find(int n) { if (n == f[n]) return n; return find(f[n]); } void merge(int a, int b) { int ra = find(a), rb = find(b); if (ra != rb) { f[rb] = f[ra]; } } bool i...

根据前序和中序构造二叉树，并使用map优化中序中找根的时间。 #include <iostream> #include <map> using namespace std; //树的节点 using Node = struct TreeNode { char val; TreeNode* left; TreeNode* right; TreeNode() : val(0), left(nullptr), right(nullptr) {} TreeNode(char x) : val(x), left(nullptr), right(nullptr) {} TreeNo...

注意题目是无向图，且输入的边，在后续输入时可能替换前面的边。也就是说边只会存在一条且是无向边。 #include <iostream> #include <vector> using namespace std; class Graph { public: //无穷 const int inf = 1e8 + 7; //邻接矩阵，使用pair是因为有花费 e[i][j].first是距离，e[i][j].second是花费 vector<vector<pair<int, int>>> e; int n; Graph(int n, ve...

#include <algorithm> #include <iostream> #include <map> #include <queue> #include <set> #include <vector> using namespace std; int main() { int n; map<string, int> degree;//入度 map<string, vector<string>> grid;//邻接矩阵 set<string> nodes; while...

#include <iostream> #include <set> #include <vector> using namespace std; const int N = 1e6 + 10; int f[N];//并查集 set<int> nodes;//有哪些节点 //查找n的根 int find(int n) { if (f[n] == n) return n; return find(f[n]); } //简单合并，不涉及高度 void merge(int a, int b) { int r1 = find(a), r2 = find(...