Quartz

hash表、并查集、最小生成树

5分钟阅读

hash表

一种以「key-value」形式存储数据的数据结构

哈希函数：f(key),把key转化成索引

数据：{1，9，31，55，87，124，251，377，456}

f(x)=x%7

indexvalue
0
11，456
29
331，87
4
5124，251，377
655

c++内部实现

unordered_set

unordered_map

并查集

合并查询的集合

  1. 初始化

    令每一个结点指向自己

    // 循环写法
for (int i = 0; i <= n; i++)
	p[i] = i;
// <numeric>库函数
iota(p, p + n + 1, 0);

  2. 查询

    int find(int x) {
	if (x != p[x])
		p[x] = find(p[x]);
	return p[x];
}
int find(int x) { return x == p[x] ? x : p[x] = find(p[x]); }

  3. 合并

    void merge(int x, int y) {
	x = find(x), y = find(y);
	if (x != y)
		p[y] = x;
}

校赛一：7-12社交集群

#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 5;
 
// 带权并查集，储存的是集合元素个数
struct DisjointSet {
    vector<int> p, val;
    DisjointSet(int n = 1e6) : p(n), val(n, 1) { iota(p.begin(), p.end(), 0); }
    int find(int x) { return x == p[x] ? x : p[x] = find(p[x]); }
    void merge(int x, int y) {
        x = find(x), y = find(y);
        if (x != y)
            p[y] = x, val[x] += val[y];
    }
};
 
int n;
set<int> a[N]; // 保存每个人的爱好
 
int main() {
    cin >> n;
    DisjointSet ds(n + 1); // 并查集为存储人的集合
    for (int i = 1, sz; i <= n; i++) {
        cin >> sz;
        cin.get();
        while (sz--) {
            int x;
            cin >> x;
            a[i].insert(x);
            // 如果自己与其他人有共同爱好，则并入同一个集合
            for (int j = 1; j < i; j++)
                if (a[j].count(x))
                    ds.merge(i, j);
        }
    }
    vector<int> ans;
    for (int i = 1; i <= n; i++)
        if (ds.find(i) == i) // 并查集的根节点，储存该集合内的人数
            ans.push_back(ds.val[i]);
    sort(ans.begin(), ans.end(), greater<int>()); // greater<int>控制逆序排序
    cout << ans.size() << endl; // 不同集合个数
    for (int i = 0; i < ans.size(); i++)
        cout << ans[i] << " \n"[i + 1 == ans.size()]; // 行末无空格输出
    return 0;
}

最小生成树

#include <bits/stdc++.h>
using namespace std;
const int N = 100, INF = 0x3f3f3f3f;
int V, E;
struct Edge
{
    int u, v, cost;
    bool operator<(const Edge &e) const { return cost < e.cost; }
};
vector<Edge> edges;
 
int p[N];
 
int find(int x) { return x == p[x] ? x : p[x] = find(p[x]); }
int kruskal()
{
    int sum = 0;
    sort(edges.begin(), edges.end());
    for (int i = 0; i < V; i++)
        p[i] = i;
    for (Edge e : edges)
        if (find(e.u) != find(e.v))
        {
            sum += e.cost;
            p[find(e.u)] = find(e.v);
        }
    return sum;
}
int main()
{
    cin >> V >> E;
    for (int i = 0, u, v, w; i < E; i++)
    {
        cin >> u >> v >> w;
        edges.push_back({u, v, w});
    }
    cout << kruskal() << endl;
    return 0;
}

Graph Editor (csacademy.com)

flowchart LR
0---|10|1
0---|3|2
0---|18|4
0---|11|5
1---|5|2
1---|1|3
2---|2|3
2---|7|5
2---|5|6
3---|2|6
4---|1|5
5---|2|6

flowchart LR
0---|3|2
1---|1|3
2---|2|3
3---|2|6
4---|1|5
5---|2|6

校赛三 7-11 秀恩爱分得快

#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 5;
 
vector<string> photo[N];
unordered_map<string, vector<int>> peo;
int n, m;
bool difsex(const string &a, const string &b) {
    return (a[0] == '-' && isdigit(b[0])) || (isdigit(a[0]) && b[0] == '-');
}
int main() {
    cin >> n >> m;
    for (int i = 1, k; i <= m; i++) {
        cin >> k;
        while (k--) {
            string x;
            cin >> x;
            photo[i].push_back(x);
            peo[x].push_back(i);
        }
    }
    string A, B;
    cin >> A >> B;
    if (m == 0) {
        cout << A << " " << B << endl;
        return 0;
    }
    map<string, double> da, db;
    for (int i : peo[A])
        for (string &x : photo[i])
            if (difsex(A, x))
                da[x] += 1.0 / photo[i].size();
 
    for (int i : peo[B])
        for (string &x : photo[i])	
            if (difsex(B, x))
                db[x] += 1.0 / photo[i].size();
 
    vector<pair<string, double>> la(da.begin(), da.end()), lb(db.begin(), db.end());
 
    auto cmp = [](const auto &a, const auto &b) -> bool {
        return a.second != b.second ? a.second > b.second : abs(stoi(a.first)) < abs(stoi(b.first));
    };
    sort(la.begin(), la.end(), cmp);
    sort(lb.begin(), lb.end(), cmp);
  
    la.erase(find_if_not(la.begin(), la.end(), [&](const auto &x) { return x.second == la[0].second; }), la.end());
    lb.erase(find_if_not(lb.begin(), lb.end(), [&](const auto &x) { return x.second == lb[0].second; }), lb.end());
 
    if (find_if(la.begin(), la.end(), [&](const auto &x) { return x.first == B; }) != la.end())
        if (find_if(lb.begin(), lb.end(), [&](const auto &x) { return x.first == A; }) != lb.end()) {
            cout << A << " " << B;
            return 0;
        }
    for (auto &i : la)
        cout << A << " " << i.first << endl;
    for (auto &i : lb)
        cout << B << " " << i.first << endl;
}

关系图谱