1 条题解
-
0
#include <iostream> #include <vector> #include <algorithm> using namespace std; int findfa(vector<int>& fa, int x) { if (fa[x] == x) return x; return fa[x] = findfa(fa, fa[x]); } void mergefa(vector<int>& fa, int a, int b) { a = findfa(fa, a); b = findfa(fa, b); if (a != b) fa[b] = a; } int main() { int n, m; cin >> n >> m; vector<int> fa(m + 1); for (int i = 1; i <= m; i++) fa[i] = i; for (int i = 0; i < n; i++) { int k; cin >> k; int first, wzpjsylai; cin >> first; for (int j = 1; j < k; j++) { cin >> wzpjsylai; mergefa(fa, first, wzpjsylai); } } // 先路径压缩 for (int i = 1; i <= m; i++) { fa[i] = findfa(fa, i); } const int INF = 1e9; vector<int> mn(m + 1, INF); // 统计每个连通块最小值 for (int i = 1; i <= m; i++) { mn[fa[i]] = min(mn[fa[i]], i); } vector<int> ans; for (int i = 1; i <= m; i++) { if (mn[i] != INF) ans.push_back(mn[i]); } sort(ans.begin(), ans.end()); for (int i = 0; i < (int)ans.size(); i++) { if (i) cout << ' '; cout << ans[i]; } cout << '\n'; return 0; }
- 1
信息
- ID
- 195
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 9
- 标签
- (无)
- 递交数
- 24
- 已通过
- 5
- 上传者