1.生成树#
1.1总体思考#
1.2 题目记录#
1.2.1 nowCoder 周赛140G 小红的生成树构造 链接 ↗#
整场周赛都是赛后补做的，这个没写出来。然后去题解讨论看了文字题解 ↗，理解思路后，感觉不是很难，然后开始写代码，but在合并过程中这个”ABCD”的类别统计碰到了麻烦，想着用set来做统计，结果越写越麻烦，遂去看官方视频题解。
然后在这个统计每个连通块的类别的时候，苯环gg用了mask来进行统计，使用数字的二进制位来表示每个类别是否存在，这样就可以通过位运算来快速地统计和合并类别，非常巧妙。
这个题目学到了二进制mask统计类别，总感觉似曾相识，但是就是自己做的时候想不到！！！
题解代码
struct DSU
{
vector<int> f, siz, mask;
DSU(int n)
{
init(n);
}
void init(int n)
{
f.resize(n);
iota(f.begin(), f.end(), 0);
siz.assign(n, 1);
mask.assign(n, 0);
}
int find(int x)
{
if (x == f[x])
{
return x;
}
f[x] = find(f[x]);
return f[x];
}
bool same(int x, int y)
{
return find(x) == find(y);
}
bool merge(int x, int y)
{
x = find(x);
y = find(y);
if (x == y)
{
return false;
}
siz[x] += siz[y];
f[y] = x;
mask[x] |= mask[y];
return true;
}
int size(int x)
{
return siz[find(x)];
}
};
void solve()
{
int n, m;
string s;
cin >> n >> m >> s;
DSU dsu(n);
for (int i = 0; i < n; i++)
{
dsu.mask[i] = (1 << (s[i] - 'A'));
}
auto check = [&](char a, char b)
{
if (a > b)
{
swap(a, b);
}
return (abs(a - b) <= 1) && !(a == 'B' && b == 'C');
};
vector<pii> ans, ext;
for (int i = 0; i < m; i++)
{
int u, v;
cin >> u >> v;
u--, v--;
if (check(s[u], s[v]))
{
if (!dsu.same(u, v))
{
dsu.merge(u, v);
ans.push_back({u, v});
}
}
else
{
ext.push_back({u, v});
}
}
for (int i = 0; i < n; i++)
{
if (dsu.find(i) != i)
{
continue;
}
if (__builtin_popcount(dsu.mask[i]) != 2)
{
cout << "No" << endl;
return;
}
}
for (auto [u, v] : ext)
{
if (!dsu.same(u, v))
{
dsu.merge(u, v);
ans.push_back({u, v});
}
}
if (dsu.size(0) != n)
{
cout << "No" << endl;
return;
}
else
{
cout << "Yes" << endl;
for (auto [u, v] : ans)
{
cout << u + 1 << " " << v + 1 << endl;
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
mainInit();
i64 t = 1;
// cin >> t;
while (t--)
{
solve();
}
return 0;
}