1. 等式方程的可满足性

题目：给定一个由表示变量之间关系的字符串方程组成的数组，每个字符串方程 equations[i] 的长度为 4，并采用两种不同的形式之一：”a==b” 或 “a!=b”。在这里，a 和 b 是小写字母（不一定不同），表示单字母变量名。
只有当可以将整数分配给变量名，以便满足所有给定的方程时才返回 true，否则返回 false。
示例：
输入：[“a==b”,”b!=c”,”c==a”]
输出：false

  1. //my solution
  3. class Solution {
  4. private:
  5. unordered_map<char,char> parent;
  8. public:
  9.     char findAncestor(char c){
  10.         char cc = c;
  11.         while(parent[c]!=0){
  12.             c= parent[c];
  13.         }
  14.         if(cc!=c) parent[cc] = c; //完全优化
  15.         return c;
  16.     }
  17.     void unionset(char a, char b){
  18.         char ac = findAncestor(a);
  19.         char bc = findAncestor(b);
  20.         if(ac != bc) parent[bc] = ac;
  21.         return ;
  22.     }
  23.     bool unionset_check_no_eq(char a, char b){
  24.         char ac = findAncestor(a);
  25.         char bc = findAncestor(b);
  26.         return bc != ac;
  27.     }
  29.     static bool cmp(string a, string b){
  30.         return a[1] > b[1];
  31.     }
  32.     bool equationsPossible(vector<string>& equations) {
  33.         int num = equations.size();
  34.         char a,b;
  35.         sort(equations.begin(),equations.end(),cmp);
  37.         for(int i=0;i<num;i++){
  38.             a = equations[i][0];
  39.             b = equations[i][3];
  40.             if(equations[i][1] == '=') unionset(a,b);
  41.             else if(!unionset_check_no_eq(a,b)){
  42.                 return false;
  43.             }
  44.         }
  45.         return true;
  46.     }
  47. };

2. 树——树形体育场紧急疏散

题目：体育场突然着火了，现场需要紧急疏散，但是过道真的是太窄了，同时只能容许一个人通过。现在知道了体育场的所有座位分布，座位分布图是一棵树，已知每个座位上都坐了一个人，安全出口在树的根部，也就是1号结点的位置上。其他节点上的人每秒都能向树根部前进一个结点，但是除了安全出口以外，没有任何一个结点可以同时容纳两个及以上的人，这就需要一种策略，来使得人群尽快疏散，问在采取最优策略的情况下，体育场最快可以在多长时间内疏散完成。
输入描述:
第一行包含一个正整数n，即树的结点数量（1<=n<=100000）。 接下来有n-1行，每行有两个正整数x，y，表示在x和y结点之间存在一条边。(1<=x，y<=n)
输出描述:
输出仅包含一个正整数，表示所需要的最短时间

示例1：
输入
6
2 1
3 2
4 3
5 2
6 1
输出
4
算法思想：
（1）将次根节点依次加入集合。
（2）求出最大的子集合。

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. class UFS{
  4. public:
  5.     vector<int> f, cnt;//f[] 保存父亲，cnt保存集合中节点数量
  6.     UFS(int n):f(n),cnt(n,1){
  7.         for(int i = 0; i < n; ++i){
  8.             f[i] = i;
  9.         }
  10.     }
  11.     int find(int i){
  12.         if(f[i] == f[f[i]])
  13.             return f[i];
  14.         else{
  15.             f[i] = f[f[i]];//折半优化
  16.             return find(f[i]);
  17.         }
  18.     }
  19.     void my_union(int x, int y){
  20.         int px = find(x);
  21.         int py = find(y);
  22.         if(px == py)    return;
  23.         else{
  24.             f[px] = py;
  25.             cnt[py] = cnt[px] + cnt[py];
  26.         }
  27.     }
  28. };
  30. int main(){
  31.     int n;
  32.     cin>>n;
  33.     UFS u(n + 1);
  34.     vector<int> root;
  35.     for(int i = 0; i < n - 1; ++i){
  36.         int x,y;
  37.         cin>>x>>y;
  38.         if(x == 1)
  39.             root.push_back(y);
  40.         else if(y == 1)
  41.             root.push_back(x);
  42.         else
  43.             u.my_union(x, y);
  44.     }
  45.     int count = 0;
  46.     for(int i = 0; i < root.size(); ++i){
  47.         count = max(count, u.cnt[u.find(root[i])]);
  48.     }
  49.     cout<<count;
  51. }