共同成交图:基于成交对的连通分量
Co-Trading Graph — Connected Components of Session Trade Pairs
开始编码监控系统观察一个交易日内有哪些 ticker 一起成交,只要符号 a 与 b 出现在任何一笔交叉成交或一篮子交易中,就发出一条无向边 [a, b]。你的任务是恢复 共同成交 ticker 的聚类——即上面这张图的连通分量。两个 ticker 属于同一聚类当且仅当存在一条共同成交边链把它们串起来;无任何边的 ticker 自成单点组件。
实现 solution(tickers, pairs) -> list[list[str]]。tickers 是全部观察到的符号集合(唯一字符串);pairs 是无向共同成交边列表。要求使用 带路径压缩与按秩合并的并查集,达到 O((N + P) * alpha(N)) 摊销复杂度——本质线性。输出组件列表:组件内部按 Python 字符串比较升序排,外层按每个组件最小 ticker 升序排。重复 pair 与自环都是幂等的空操作;pairs 中出现 tickers 之外的 ticker 时抛 ValueError。
举例:solution(["AAPL", "MSFT", "GOOG", "AMZN", "TSLA"], [["AAPL", "MSFT"], ["GOOG", "AMZN"]]) 返回 [["AAPL", "MSFT"], ["AMZN", "GOOG"], ["TSLA"]]。两个共同成交聚类加一个孤立 ticker;外层按各组件最小 ticker 排序(AAPL < AMZN < TSLA)。
实践背景
共同成交图的连通分量是 执行场所的篮子检测 与 聚类层因子构造 的基础原语。当行情打印出现一波相关交叉成交——比如某养老金通过单一经纪商减持一个行业篮子——该交易日的共同成交图会出现一个覆盖所有行业成员的巨型组件,下游监控就能把整篮当作一个单位提起,而不必逐笔追踪每个成交。同样的原语在因子研究里也常见:把"同一经纪商一篮子在滚动窗口内同时出现"作为边,跑一次连通分量,把组件 ID 当作类别因子或跨资产风险模型的图先验。这里用并查集是因为边通常是 *流式* 到达的——每条新打印的成交都是一条新边——而 DSU 每次合并 O(alpha(N)) 的摊销代价让聚类结构能持续维护,无需重建邻接表。BFS/DFS 是等价的批处理算法;两者都该在工具箱里,但图是在线增长时优先选 DSU。
约束条件
- 0 ≤ `len(tickers)` ≤ 10000(全部观察到的 ticker 集合;每条都是唯一的非空字符串)
- 0 ≤ `len(pairs)` ≤ 100000(每对 `[a, b]` 是一条无向共同成交边)
- 出现在 `pairs` 中的每个 ticker 必须存在于 `tickers` 中;否则函数抛 `ValueError`
- 允许重复 pair(幂等——第二次 union 直接 early-exit)
- 允许自环(`a == b`)(空操作 union——`find(a) == find(a)` 立即返回)
- 输出是 `list[list[str]]`;每个内部组件按 Python 字符串比较排序;外层按每个组件最小 ticker 字典序排序;比较器为精确相等(`kind: exact`、`ordered: true`)
样例
Case 1 · statement-example: empty universe yields no components
输入: [[],[]]
期望: []
宇宙为空时没有节点也没有边,直接返回空的组件列表。
Case 2 · statement-example: single ticker with no edges is its own component
输入: [["AAPL"],[]]
期望: [["AAPL"]]
单个 ticker 不与任何边相关,自身就是一个孤立的组件。
Case 3 · three disconnected tickers give three singletons sorted by min ticker
输入: [["MSFT","AAPL","GOOG"],[]]
期望: [["AAPL"],["GOOG"],["MSFT"]]
无边时所有节点都是孤点,组件列表按每个组件最小 ticker 字典序排序:AAPL < GOOG < MSFT。
Case 4 · statement-example: two tickers connected by one edge
输入: [["AAPL","MSFT"],[["AAPL","MSFT"]]]
期望: [["AAPL","MSFT"]]
一条边把 AAPL 和 MSFT 联通成单一组件,组件内部按字典序排序输出 [AAPL, MSFT]。
Case 5 · statement-example: chain edges fully connect three tickers
输入: [["AAPL","MSFT","GOOG"],[["AAPL","MSFT"],["MSFT","GOOG"]]]
期望: [["AAPL","GOOG","MSFT"]]
AAPL-MSFT 和 MSFT-GOOG 两条边通过 MSFT 串连成单一组件,排序后为 [AAPL, GOOG, MSFT]。
Case 6 · statement-example: two components plus an isolated singleton
输入: [["AAPL","MSFT","GOOG","AMZN","TSLA"],[["AAPL","MSFT"],["GOOG","AMZN"]]]
期望: [["AAPL","MSFT"],["AMZN","GOOG"],["TSLA"]]
AAPL-MSFT 一组,GOOG-AMZN 一组,TSLA 无边自成一组;按组件最小 ticker 排序:AAPL < AMZN < TSLA。
Case 7 · duplicate pair is idempotent under union-find
输入: [["A","B","C"],[["A","B"],["A","B"],["B","A"]]]
期望: [["A","B"],["C"]]
重复合并同一对节点是幂等的:A 与 B 已在同一组件,后两次合并 early-return 不影响结构。C 仍然孤立。
Case 8 · self-edge is a no-op union
输入: [["A","B","C"],[["A","A"],["B","C"]]]
期望: [["A"],["B","C"]]
自环 [A, A] 调用 union 时 find(A)==find(A),直接 early-return,不连接任何东西。B-C 正常合并。
Case 9 · star topology — hub edges fuse every spoke into one component
输入: [["HUB","S1","S2","S3","S4"],[["HUB","S1"],["HUB","S2"],["HUB","S3"],["HUB","S4"]]]
期望: [["HUB","S1","S2","S3","S4"]]
星型拓扑:每条辐条都通过 HUB 与其他辐条相连,最终所有 5 个节点合成一组。
Case 10 · edge order does not affect output sort
输入: [["Z","Y","X","W"],[["Z","Y"],["X","W"],["Y","X"]]]
期望: [["W","X","Y","Z"]]
边的输入顺序不影响最终连通性。最终 Z-Y-X-W 全部连通,组件内部按字典序输出 [W, X, Y, Z]。
Case 11 · mixed components with singletons sort by lexicographic min
输入: [["ZULU","ALPHA","BRAVO","CHARLIE","DELTA"],[["ZULU","BRAVO"],["CHARLIE","DELTA"]]]
期望: [["ALPHA"],["BRAVO","ZULU"],["CHARLIE","DELTA"]]
ALPHA 单点;BRAVO-ZULU 一组,组内最小为 BRAVO;CHARLIE-DELTA 一组,组内最小为 CHARLIE。外层按 ALPHA < BRAVO < CHARLIE 排序。
最近提交
还没有提交记录。
编码区
实现 solution(...)。本地运行当前支持 Python 可见样例；服务端提交会运行可见样例和隐藏测试。
默认展示公开样例。点击「运行样例」后会在这里显示实际输出；点击「提交评测」会进入隐藏测试。
Case 1 · statement-example: empty universe yields no components
输入: [[],[]]
期望: []
宇宙为空时没有节点也没有边,直接返回空的组件列表。
Case 2 · statement-example: single ticker with no edges is its own component
输入: [["AAPL"],[]]
期望: [["AAPL"]]
单个 ticker 不与任何边相关,自身就是一个孤立的组件。
Case 3 · three disconnected tickers give three singletons sorted by min ticker
输入: [["MSFT","AAPL","GOOG"],[]]
期望: [["AAPL"],["GOOG"],["MSFT"]]
无边时所有节点都是孤点,组件列表按每个组件最小 ticker 字典序排序:AAPL < GOOG < MSFT。
Case 4 · statement-example: two tickers connected by one edge
输入: [["AAPL","MSFT"],[["AAPL","MSFT"]]]
期望: [["AAPL","MSFT"]]
一条边把 AAPL 和 MSFT 联通成单一组件,组件内部按字典序排序输出 [AAPL, MSFT]。
Case 5 · statement-example: chain edges fully connect three tickers
输入: [["AAPL","MSFT","GOOG"],[["AAPL","MSFT"],["MSFT","GOOG"]]]
期望: [["AAPL","GOOG","MSFT"]]
AAPL-MSFT 和 MSFT-GOOG 两条边通过 MSFT 串连成单一组件,排序后为 [AAPL, GOOG, MSFT]。
Case 6 · statement-example: two components plus an isolated singleton
输入: [["AAPL","MSFT","GOOG","AMZN","TSLA"],[["AAPL","MSFT"],["GOOG","AMZN"]]]
期望: [["AAPL","MSFT"],["AMZN","GOOG"],["TSLA"]]
AAPL-MSFT 一组,GOOG-AMZN 一组,TSLA 无边自成一组;按组件最小 ticker 排序:AAPL < AMZN < TSLA。
Case 7 · duplicate pair is idempotent under union-find
输入: [["A","B","C"],[["A","B"],["A","B"],["B","A"]]]
期望: [["A","B"],["C"]]
重复合并同一对节点是幂等的:A 与 B 已在同一组件,后两次合并 early-return 不影响结构。C 仍然孤立。
Case 8 · self-edge is a no-op union
输入: [["A","B","C"],[["A","A"],["B","C"]]]
期望: [["A"],["B","C"]]
自环 [A, A] 调用 union 时 find(A)==find(A),直接 early-return,不连接任何东西。B-C 正常合并。
Case 9 · star topology — hub edges fuse every spoke into one component
输入: [["HUB","S1","S2","S3","S4"],[["HUB","S1"],["HUB","S2"],["HUB","S3"],["HUB","S4"]]]
期望: [["HUB","S1","S2","S3","S4"]]
星型拓扑:每条辐条都通过 HUB 与其他辐条相连,最终所有 5 个节点合成一组。
Case 10 · edge order does not affect output sort
输入: [["Z","Y","X","W"],[["Z","Y"],["X","W"],["Y","X"]]]
期望: [["W","X","Y","Z"]]
边的输入顺序不影响最终连通性。最终 Z-Y-X-W 全部连通,组件内部按字典序输出 [W, X, Y, Z]。
Case 11 · mixed components with singletons sort by lexicographic min
输入: [["ZULU","ALPHA","BRAVO","CHARLIE","DELTA"],[["ZULU","BRAVO"],["CHARLIE","DELTA"]]]
期望: [["ALPHA"],["BRAVO","ZULU"],["CHARLIE","DELTA"]]
ALPHA 单点;BRAVO-ZULU 一组,组内最小为 BRAVO;CHARLIE-DELTA 一组,组内最小为 CHARLIE。外层按 ALPHA < BRAVO < CHARLIE 排序。