企业官网建设流程全解析

仿制网站,163企业邮箱格式,关键词推广,西安是哪个省属于哪个市题目描述#xff1a;现在有 n 个人#xff0c;他们之间有两种关系#xff1a;朋友和敌人。我们知道#xff1a;一个人的朋友的朋友是朋友一个人的敌人的敌人是朋友现在要对这些人进行组团。两个人在一个团体内当且仅当这两个人是朋友。请求出这些人中最多可能有的团体数。输…题目描述现在有 n 个人他们之间有两种关系朋友和敌人。我们知道一个人的朋友的朋友是朋友一个人的敌人的敌人是朋友现在要对这些人进行组团。两个人在一个团体内当且仅当这两个人是朋友。请求出这些人中最多可能有的团体数。输入格式第一行输入一个整数 n 代表人数。第二行输入一个整数 m 表示接下来要列出 m 个关系。接下来 m 行每行一个字符 opt 和两个整数 p,q分别代表关系朋友或敌人有关系的两个人之中的第一个人和第二个人。其中 opt 有两种可能如果 opt 为F则表明 p 和 q 是朋友。如果 opt 为E则表明 p 和 q 是敌人。输出格式一行一个整数代表最多的团体数。输入输出样例输入 #1复制6 4 E 1 4 F 3 5 F 4 6 E 1 2输出 #1复制3说明/提示对于 100% 的数据2≤n≤10001≤m≤50001≤p,q≤n。思路题目简单来说就是给出几对关系有朋友关系也有敌对关系要我们输出最终团体的数量。看到这种说两两关系的题我们可以想到用并查集来做按题目的说法我们可以知道朋友的敌人的朋友就是敌人敌人的敌人是朋友都是朋友说明在一个团体。那么我们可以考虑扩展两倍n做一个虚拟节点n1~2n的操作一半朋友一半敌人也就是n*2。然后是朋友就正常合并他们为一个团体合并x,y,否则就是敌对那么有一对关系也就是x讨厌yy讨厌x那么我们可以进行两个合并即合并xny合并ynx。最后统计1到n的根节点数量也就是团体数量也就是答案。举个例子假设n2m1操作是E 1 21 和 2 是敌人。初始化saki[1]1, saki[2]2, saki[3]3, saki[4]4执行he(12, 2)→he(3, 2)此时saki[fin(3)] fin(2)→saki[2] 23 的根变成 2执行he(22, 1)→he(4, 1)此时saki[fin(4)] fin(1)→saki[1] 14 的根变成 1主播的代码参考:#include iostream #includequeue #includealgorithm #includemap #includevector #includeset #includestack #includestring #includemath.h #include iomanip #includeunordered_map #include unordered_set #includearray #define gets(S) fgets(S,sizeof(S),stdin) #define ll long long const ll N 1e6 5; const ll Max 0x3f3f3f3f; using namespace std; ll n, m, saki[N]; ll fin(ll x) { return saki[x] x ? x : saki[x] fin(saki[x]); } void he(ll x, ll y) { saki[fin(x)] fin(y); } int main() { cin n m; for (int i 1; i n * 2; i) { saki[i] i; } char c; ll x, y; for (int i 1; i m; i) { cin c; cin x y; if (c F) { he(x, y); } else { he(x n, y); he(y n, x); } } ll ans 0; for (int i 1; i n; i) { if (fin(i) i) { ans; } } cout ans; return 0; }