P1481




```cpp
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct TrieNode {
    TrieNode* children[26];
    int depth;

    TrieNode() {
        for (int i = 0; i < 26; i++) {
            children[i] = nullptr;
        }
        depth = 0;
    }
};

int findLongestWordChain(vector<string>& words) {
    sort(words.begin(), words.end());
    TrieNode* root = new TrieNode();
    int maxLength = 0;

    for (const string& word : words) {
        TrieNode* cur = root;
        int length = 0;

        for (char c : word) {
            int index = c - 'a';
            if (cur->children[index] == nullptr) {
                cur->children[index] = new TrieNode();
            }
            cur = cur->children[index];
            length = max(length, cur->depth);
        }

        cur->depth = length + 1;
        maxLength = max(maxLength, cur->depth);
    }

    return maxLength;
}

int main() {
    int n;
    cin >> n;

    vector<string> words;
    for (int i = 0; i < n; i++) {
        string word;
        cin >> word;
        words.push_back(word);
    }

    int result = findLongestWordChain(words);
    cout << result << endl;

    return 0;
}

```

解法二  dp

```cpp
#include <iostream>
#include <vector>
#include <string>
using namespace std;

int findLongestWordChain(vector<string> words) {
    int n = words.size();
    vector<int> dp(n, 1);

    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (words[i].find(words[j]) == 0) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
    }

    int maxChainLength = 0;
    for (int i = 0; i < n; i++) {
        maxChainLength = max(maxChainLength, dp[i]);
    }

    return maxChainLength;
}

int main() {
    int n;
    cin >> n;
    vector<string> words(n);

    for (int i = 0; i < n; i++) {
        cin >> words[i];
    }

    sort(words.begin(), words.end()); // Sort the words lexicographically

    int result = findLongestWordChain(words);
    cout << result << endl;

    return 0;
}

```

trie树

B3616




```cpp
#include <iostream>

class Queue {
private:
    int* data;
    int front;
    int rear;
    int capacity;
    int size;

public:
    Queue(int cap) {
        data = new int[cap];
        capacity = cap;
        front = rear = -1;
        size = 0;
    }

    ~Queue() {
        delete[] data;
    }

    void push(int x) {
        if (size == capacity) {
            std::cout << "ERR_CANNOT_PUSH" << std::endl;
        } else {
            rear = (rear + 1) % capacity;
            data[rear] = x;
            if (size == 0) {
                front = rear;
            }
            size++;
        }
    }

    void pop() {
        if (size == 0) {
            std::cout << "ERR_CANNOT_POP" << std::endl;
        } else {
            front = (front + 1) % capacity;
            size--;
        }
    }

    void query() {
        if (size == 0) {
            std::cout << "ERR_CANNOT_QUERY" << std::endl;
        } else {
            std::cout << data[front] << std::endl;
        }
    }

    int getSize() {
        return size;
    }
};

int main() {
    int n;
    std::cin >> n;

    Queue q(100); // 假设队列最大容量为100

    for (int i = 0; i < n; i++) {
        int op;
        std::cin >> op;
        if (op == 1) {
            int x;
            std::cin >> x;
            q.push(x);
        } else if (op == 2) {
            q.pop();
        } else if (op == 3) {
            q.query();
        } else if (op == 4) {
            std::cout << q.getSize() << std::endl;
        }
    }

    return 0;
}

```

队列

看到要计算最短时间就知道要排序

[并查集模板](https://www.luogu.com.cn/training/3065#problems)


```cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Road {
    int from, to, repairTime;
};

vector<int> parent;

int find(int x) {
    if (parent[x] == x) {
        return x;
    }
    return parent[x] = find(parent[x]);
}

bool unite(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);
    if (rootX != rootY) {
        parent[rootX] = rootY;
        return true; // 返回 true 表示成功合并
    }
    return false; // 返回 false 表示已经在同一集合中
}

int main() {
    int N, M;
    cin >> N >> M;

    vector<Road> roads(M);

    for (int i = 0; i < N; ++i) {
        parent.push_back(i); // 初始化每个村庄独立成集合
    }

    for (int i = 0; i < M; ++i) {
        cin >> roads[i].from >> roads[i].to >> roads[i].repairTime;
        roads[i].from--;
        roads[i].to--;
    }

    sort(roads.begin(), roads.end(), [](const Road &a, const Road &b) {
        return a.repairTime < b.repairTime;
    });

    int components = N;
    int earliestTime = -1;

    for (int i = 0; i < M; ++i) {
        if (unite(roads[i].from, roads[i].to)) {
            components--;
            earliestTime = roads[i].repairTime;
            if (components == 1) {
                break; // 所有村庄已连通
            }
        }
    }

    if (components == 1) {
        cout << earliestTime << endl;
    } else {
        cout << -1 << endl;
    }

    return 0;
}


```

P1111

反并查集
如果是朋友，合并a和b。

如果是敌人，合并a+n和b，b+n和a(a的敌人是b，b的敌人是a)

代码






```go
#include <iostream>
#include <vector>
using namespace std;

vector<int> parent;

int find(int x) {
    if (x == parent[x]) {
        return x;
    }
    return find(parent[x]);
}

void unite(int x, int y) {
    int root_x = find(x);
    int root_y = find(y);
    if (root_x != root_y) {
        parent[root_x] = root_y;
    }
}

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

    parent.resize(2 * n + 1);

    for (int i = 1; i <= 2 * n+1; ++i) {
        parent[i] = i; // 初始化，每个人独立成团
    }

    for (int i = 1; i <= m; ++i) {
        char opt;
        int p, q;
        cin >> opt >> p >> q;
        if (opt == 'F') { // 朋友关系
            unite(p, q);
        } else { // 敌人关系
            // 如果两者不在同一个团体，将敌人的团体合并到朋友的团体
            if (find(p) != find(q)) {
                unite(q + n,p);
                unite(p + n,q);
            }
        }
    }

    int maxGroups = 0;
    for (int i = 1; i <= n; ++i) {
        if (find(i) == i) {
            maxGroups++;
        }
    }

    cout << maxGroups << endl;
    return 0;
}

```

P1892

并查集，用map映射下，然后记得记录父亲


```cpp
#include <cstdio>
#include <iostream>
#include <map>
using namespace std;



map<string, string> p;

string find(string x) {
    if (x != p[x]) 
        p[x] = find(p[x]);
    return p[x];
}

string s, s1;

int main() {
    char ch;
    cin >> ch;
    while (ch != '$') {
        cin >> s;
        if (ch == '#') {
            s1 = s;
            if (p[s] == "") p[s] = s;
        } else if (ch == '+') {
            p[s] = s1;
        } else {
            cout << s << ' ' << find(s) << endl;
        }
        cin >> ch;
    }
    return 0;
}


```