鏈接：https://ac.nowcoder.com/acm/contest/11334/J
來源：牛客網
題目描述
牛牛苦練武功絕學——輕功水上漂，最終沒有練成，但是他學會了在樹上行走的本領，
這天，牛牛落入了敵人的陷阱，身后有巨石追擊，面前有n個點，n-1條邊連成一張連通圖（一棵樹），現在牛牛必須立馬選擇進入這張圖中，但是牛牛發現，這張圖有兩種不同的點，一旦進入一個點，所有與該點不同型別的點都會消失（相連的邊也會消失），牛牛只能走到有邊相連的點，牛牛想要自己盡量有更多的點可以活動，那么他可以進入哪些點？
輸入描述:
第一行有一個正整數 n {}n 表示共有 n {}n 個點（n\leq2×10^5）（n≤2×10
5
）
第二行有n{}n 個數 a_ia
i
?
表示兩種型別的點（0 \leq a_i\leq 1）（0≤a
i
?
≤1）
接下來 n-1{}n?1行每行有兩個正整數u，v（u，v\leq n）u，v（u，v≤n） 表示 u{}u 和 v{}v 之間有一條邊
輸出描述:
第一行輸出可以進入的點的個數
第二行從小到大輸出這些點的編號
示例1
輸入
復制
3
1 1 0
1 2
1 3
輸出
復制
2
1 2
說明
落到1和2的情況可以有2的移動位置，是最大的
示例2
輸入
復制
4
1 1 0 0
1 2
2 3
3 4
輸出
復制
4
1 2 3 4
說明
不論落到哪個點，都有2個位置可以移動
如果兩個點的型別是一樣的話，就把他們放到同一個集合里面，最后看最大的集合個數是多少，最后看有多少點的集合和最大集合的個數是相等的
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 2e5 + 10;
int p[N], a[N], cnt[N];
int find(int x){
if (x != p[x]) p[x] = find(p[x]);
return p[x];
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i ++){
p[i] = i;
cnt[i] = 1;
}
for (int i = 1; i <= n; i ++){
scanf("%d", &a[i]);
}
for (int i = 1; i < n; i ++){
int x, y;
scanf("%d%d", &x, &y);
if (a[x] != a[y]) continue;
else{
int pa = find(x);
int pb = find(y);
// cout << "---------" << endl;
if (pa != pb){
p[pa] = pb;
cnt[pb] += cnt[pa];
}
}
}
int ans = 0;
int cnt1 = 0;
for (int i = 1; i <= n; i ++){
int p = find(i);
// cout << "----" << endl;
ans = max(cnt[p], ans);
}
vector<int> v;
for (int i = 1; i <= n; i ++){
int p = find(i);
if (cnt[p] == ans){
v.push_back(i);
}
}
cout << v.size() << endl;
for (int i = 0; i < v.size(); i ++){
cout << v[i] << " ";
}
cout << endl;
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/248621.html
標籤：其他