洛谷p1892团伙(代码片段)

关键词：

6
4
E 1 4
F 3 5
F 4 6
E 1 2

3

思路：并查集     难度：普及+/提高

//可读性应该比较高吧。。。
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int n, m, tot;
int fa[1005], foe[1005], ff[1005];
//fa[]记录每个人的上一层，foe[]记录每个人的敌人，ff[]记录有多少人是根
char c;
int find(int x)         //寻找根节点
    return fa[x]==x ? x : fa[x]=find(fa[x]);

void merge(int u, int v)         //merge 合并
    int x = find(u), y = find(v);
    if(x == y) return ;
    fa[x] = y;
    tot--;

int main() 
    int maxn = -1;
    scanf("%d%d", &n, &m);
    tot = n;        //突然发现这个好像没啥用qwq
    for(int i = 1; i <= n; i++) fa[i] = i;
    for(int i = 1; i <= m; i++) 
        cin >> c;
        int u, v;
        if(c == ‘F‘)         //如果是朋友，直接合并
            scanf("%d%d", &u, &v);
            merge(u, v);
        
        if(c == ‘E‘)         //分别寻找每个人是否有另一个敌人，然后进行合并
            scanf("%d%d", &u, &v);
            if(foe[u] != 0) merge(v, foe[u]);
            if(foe[v] != 0) merge(u, foe[v]);
            foe[u] = v; foe[v] = u;
        
    
    for(int i = 1; i <= n; i++) 
        int t = find(fa[i]);
        ff[t]++;        //寻找有哪些人作为根节点
        if(t > maxn) maxn = t;
    
    int sum = 0;
    for(int i = 1; i <= maxn; i++) if(ff[i] != 0) sum++;        //计数
    printf("%d", sum);
    return 0;

p1892[boi2003]团伙并查集(代码片段)

...我的朋友；我敌人的敌人也是我的朋友。两个强盗是同一团伙的条件是当且仅当他们是朋友。现在给你一些关于强盗们的信息，问你最多有多少个强盗团伙。输入输出格式输入格式： 输入文件gangs.in的第一行是一个整数N(2<... 查看详情

解题报告：luogup1892(代码片段)

题目链接：P1892[BOI2003]团伙最近懒死了。和P1525关押罪犯和相似，也要有一个记录敌人信息的数组。这里对这个数组有个好些的理解：记录敌人集合中的任意一个，由于并查集的性质，其他的也随之确定。注意的是，在两个团伙... 查看详情

团伙封锁阳光大学(代码片段)

团伙#include<iostream>#include<cstdio>#include<algorithm>usingnamespacestd;constintmaxn=2e5+7;intfa[maxn],en[maxn],size[maxn];intn,m;intfind(intx)if(fa[x]==x)returnx;returnfa[x]=find( 查看详情

题解团伙(代码片段)

...是我的朋友；    所有是朋友的人组成一个团伙。告诉你关于这n个人的m条信息，即某两个人是朋友，或 查看详情

题解打击犯罪(代码片段)

...目描述    某个地区有n（n≤1000）个犯罪团伙，当地警方按照他们的危险程度由高到低给他们编号为1至n，他们有些团伙之间有直接联系，，但是任意两个团伙都可以通过直接或间接的方式联系，这样这里就形成了... 查看详情

codevs5971打击犯罪(代码片段)

题目描述Description  某个地区有n(n<=1000)个犯罪团伙，当地警方按照他们的危险程度由高到低给他们编号为1-n，他们有些团伙之间有直接联系，但是任意两个团伙都可以通过直接或间接的方式联系，这样这里就形成了一个... 查看详情

动规(18)-并查集基础题——团伙(代码片段)

...我敌人的敌人是我的朋友；所有是朋友的人组成一个团伙。告诉你关于这N个人的M条信息，即某两个人是朋友，或者某两个人是敌人，请你编写一个程序，计算出这个城市最多可能 查看详情

动规(18)-并查集基础题——团伙(代码片段)

...我敌人的敌人是我的朋友；所有是朋友的人组成一个团伙。告诉你关于这N个人的M条信息，即某两个人是朋友，或者某两个人是敌人，请你编写一个程序，计算出这个城市最多可能 查看详情

动规(20)-并查集基础题——打击犯罪(代码片段)

【问题描述】 　某个地区有n(n<=1000)个犯罪团伙，当地警方按照他们的危险程度由高到低给他们编号为1-n，他们有些团伙之间有直接联系，但是任意两个团伙都可以通过直接或间接的方式联系，这样这里就形... 查看详情

动规(20)-并查集基础题——打击犯罪(代码片段)

【问题描述】 　某个地区有n(n<=1000)个犯罪团伙，当地警方按照他们的危险程度由高到低给他们编号为1-n，他们有些团伙之间有直接联系，但是任意两个团伙都可以通过直接或间接的方式联系，这样这里就形... 查看详情

动规(20)-并查集基础题——打击犯罪(代码片段)

【问题描述】 　某个地区有n(n<=1000)个犯罪团伙，当地警方按照他们的危险程度由高到低给他们编号为1-n，他们有些团伙之间有直接联系，但是任意两个团伙都可以通过直接或间接的方式联系，这样这里就形... 查看详情

bzoj1370:[baltic2003]gang团伙（luogu1892）（种类并查集）(代码片段)

题面：　　bzoj题面有误，还是看luogu的吧　　https://www.luogu.org/problemnew/show/P1892题解：　　种类并查集。。　　因为有敌人的敌人是朋友这个条件，所以需要一个中转点。。　　因此，将每个点拆成两个点，一个是朋友点，另一... 查看详情

真·抢显卡！四川一团伙持40cm长刀入室抢劫50余张显卡，总价值超10万元(代码片段)

👇👇关注后回复 “进群” ，拉你进程序员交流群👇👇来源：量子位QbitAI这年头，有显卡也能招来祸事了？？？没错，不仅可能被入室抢劫，而且还会受到持刀威胁。别不信，... 查看详情

洛谷2458(代码片段)

f[now][0]表示以当前点为根，且要取该点，满足条件的最小#include<cstdio>#include<cctype>#include<cstring>#include<algorithm>usingnamespacestd;inthead[1501],to[1501],nex[1501],val[1501],indg[1501],f[150 查看详情

洛谷3348(代码片段)

可持久化线段树模板1.结构体的打法#include<cstdio>#include<cctype>#include<algorithm>usingnamespacestd;constintmaxn=200010;structdataintl,r,sz;tr[maxn<<5];intn,m,cnt,key,a[maxn],rk[maxn],id[m 查看详情

求细胞数量-洛谷(代码片段)

求细胞数量-洛谷法1：BFS#include<iostream>#include<cstdio>usingnamespacestd;intdx[4]=-1,0,1,0;intdy[4]=0,1,0,-1;//左、右、上、下intbz[100][100],num=0,n,m;voiddoit(intp,intq)intx,y,t,w,i; 查看详情

洛谷p1535游荡的奶牛(代码片段)

P1535游荡的奶牛题目描述Searchingfortheverybestgrass,thecowsaretravellingaboutthepasturewhichisrepresentedasagridwithNrowsandMcolumns(2<=N<=100;2<=M<=100).KeenobserverFarmerJohnhasrecordedBessie‘spo 查看详情

洛谷p1816忠诚(代码片段)

https://www.luogu.org/problemnew/show/1816st表模板#include<cstdio>#include<algorithm>usingnamespacestd;typedeflonglongLL;LLm,n;LLa[100100],d[100100][20];intmain()LLi,j,l,r,k;scanf("%lld%lld" 查看详情