首页 > 其他分享 >P5214 [SHOI2014] 神奇化合物

P5214 [SHOI2014] 神奇化合物

时间:2024-05-09 23:44:05浏览次数:22  
标签:P5214 int ll ch vec SHOI2014 now find 神奇

题目链接:https://www.luogu.com.cn/problem/P5214

题意:给定一张无向图,分别进行以下操作:

Q:询问图中有多少连通块;

A u v :代表在 u v之间链接一条边;

D u v:代表删除链接u v的边。

做法:考虑到题目数据范围较小,直接用邻接表存边即可。
可以发现有些点是不会进行改变的,可以讲在线询问转成离线,通过并查集将不会改变的点进行缩点,缩点处理之后建立一张新图。由于数据范围小,对于每次查询操作在图上进行暴力搜索连通块即可。增边删边操作只需对邻接表加减操作即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
#define mp make_pair
#define ull unsigned long long
inline int gcd(int a, int b){return b == 0 ? a : gcd(b, a % b);}
inline int lcm(int a, int b){return a / gcd(a, b) * b;}
const ll mod = 998244353;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
inline int read()
{
int X=0; bool flag=1; char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') flag=0; ch=getchar();}
while(ch>='0'&&ch<='9') {X=(X<<1)+(X<<3)+ch-'0'; ch=getchar();}
if(flag) return X;
return ~(X-1);
}
#define maxn 5010
#define N 10010
#define int long long
int vec[maxn][maxn];
char c[N];
int p[maxn];
int l[N],r[N];
int x[200010],y[200010];
vector<int> g[maxn];
int find(int x){
    if(p[x]!=x)
    {
        p[x]=find(p[x]);
    }
    return p[x];
}
void uni(int a,int b)
{
    int x=find(a);
    int y=find(b);
    if(x!=y)
    {
        p[x]=y;
    }
}
int vis[maxn];
inline void dfs(int now)
{
    vis[now]=1;
    for(auto to:g[now])
    {
        if(!vis[to]&&vec[now][to])
        {
            dfs(to);
        }
    }
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        p[i]=i;
    }
    for(int i=1;i<=m;i++)
    {
        cin>>x[i]>>y[i];
        vec[x[i]][y[i]]=vec[y[i]][x[i]]=1;
    }
    int q;
    cin>>q;
    for(int i=1;i<=q;i++)
    {
        cin>>c[i];
        if(c[i]!='Q')
        {
            cin>>l[i]>>r[i];
        }
        if (c[i]=='D')
        {
            vec[l[i]][r[i]]=vec[r[i]][l[i]]=0;
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(vec[i][j])
            {
                uni(i,j);
            }
        }
    }
    memset(vec,0,sizeof(vec));
    for(int i=1;i<=m;i++)
    {
        if(!vec[find(x[i])][find(y[i])])
        {
            g[find(x[i])].push_back(find(y[i]));
            g[find(y[i])].push_back(find(x[i]));
        }
        vec[find(x[i])][find(y[i])]++;
        vec[find(y[i])][find(x[i])]++;
    }
    for(int i=1;i<=q;i++)
    {
        if(c[i]=='D')
        {
            vec[find(l[i])][find(r[i])]=vec[find(r[i])][find(l[i])]=max(1ll*0,
            vec[find(l[i])][find(r[i])]-1);
        }
        else if(c[i]=='A')
        {
            if(!vec[find(l[i])][find(r[i])])
            {
                g[find(l[i])].push_back(find(r[i]));
                g[find(r[i])].push_back(find(l[i]));
            }
            vec[find(l[i])][find(r[i])]++;
            vec[find(r[i])][find(l[i])]++;
        }
        else
        {
            memset(vis,0,sizeof(vis));
            int ans=0;
            for(int j=1;j<=n;j++)
            {
                if(!vis[find(j)])
                {
                    dfs(find(j));
                    ans++;
                }
            }
            cout<<ans<<endl;
        }
    }
    return 0;

}

标签:P5214,int,ll,ch,vec,SHOI2014,now,find,神奇
From: https://www.cnblogs.com/captainfly/p/18183342

相关文章

  • 化腐朽为神奇!揭开ISP图像处理的神秘面纱,基于瑞芯微RK3568J工业平台!
    ISP图像处理前后图像对比化腐朽为神奇!经过ISP图像处理的图片前后对比是如此惊人!从下图中可以观察到,未经处理的原始图像偏绿且暗淡,而经ISP图像处理的图像能够清晰地还原现场真实的颜色细节! 图1 原始图像显示效果 图2 经ISP图像处理后显示效果  ISP说明......
  • 一道神奇的面试题---无序数组排序后的最大相邻差
    一:概述这个算法的面试题目是:有一个无序整型数组,如何求出该数组排序后的任意两个相邻元素的最大差值?要求时间和空间复杂度尽可能低。  二:具体说明<1>第一种解法(初步解法)这个解法的大致思路:使用任意一种时间复杂度为O(nlogn)的排序算法(如快速......
  • xxx,一个神奇的 Python 库
    前几天,我在《技术周刊的转变:如何平衡热爱与现实?》一文里写过国内Python自媒体圈在近几年的两个现象(仅个人观感,无科学数据支撑):Python广告投放出现断崖式萎缩Python大号出现很多改名/转行本文想继续分享我观察到的另一个挺有意思的现象。如果你能从中受到一些启发,进而为自......
  • 异或运算在算法中的神奇应用
    1.什么是异或两个二进制数进行异或运算时,每一位上的数相同则结果为0,不同则结果为1。示例:6^7=?转化成二进制:6=1107=1116^7=110^111=001=1简单记:异或就是二进制的无进位相加。还有个同或运算:相同为1,不同为0,和异或是反的。2.异或运算的特性任何数与0异或,结果还是这......
  • 神奇!autoTrimCurve(curve,parameter1)中参数parameter1的意义
    autoTrimCurve命令解释使用python进行ABAQUS二次开发时,建立草图用到自动裁剪命令,rpy文件中记录的是s.autoTrimCurve(curve1=g[4],point1=(-12.5237464904785,0.153462409973145))关键词 point1需要输入曲线上某点的坐标值,即一对浮点数由于我的需求大量参数化建模,每次生......
  • 临床反馈:久服桂附理中丸和桂附地黄丸有神奇的“除臭”功效 转载
    关于人体的各种臭,是个比较尴尬的话题。 而且,现在社会上对各种“臭症”有非常严重的误区。比如,小孩子口臭,大人的第一反应就是“是不是上火了”;比如,很多人脚臭,第一反应就是“是不是真菌感染”;再比如,很多人体臭汗臭,第一反应就是“是不是湿气太重”。 上述都是误区。 那么,为......
  • Data.olllo解密:秒数转换为日期格式的神奇技能!
    引言:时间是数据世界中不可或缺的一环,而将秒数转换为易读的日期格式往往是数据处理中的一大挑战。但是,有了Data.olllo,这一任务将变得异常简单!功能介绍:Data.olllo的秒数转换功能可以让您轻松地将秒数格式的时间转换为标准的年月日时分秒的日期格式。这个功能不仅能够提高数据......
  • 时间的守护者:无硫手指套的神奇传说
    在钟表制造的世界里,有一个神奇的工具被誉为“精工制表良器”——那就是无硫手指套。这并不是一个普通的故事,而是一段讲述质量、技术和关怀的传奇。很久以前,在一个钟表制造工坊里,技师们为了追求完美,不断地探索着提升产品品质的方法。他们发现,即便是最微小的细节也可能对产品造......
  • Arrow,一个超神奇的python库
    From: https://mp.weixin.qq.com/s/A3oa1tt2ef7p0MzLQQPp4A--------------------------------------------------------------------------------------https://github.com/arrow-py/arrow什么是Arrow?Arrow是一个Python的时间处理库,它提供了更加简单、清晰的方式来创建、操作......
  • 晶片:科技巨擘的神奇魔法
    在现代科技的浪潮中,晶片扮演着不可或缺的角色,它们是数字世界的魔法师,为我们的生活带来了巨大变革。从智能手机到超级计算机,从家用电器到航天器,晶片的存在无处不在,它们的发展也不断推动着科技的进步。晶片的基础构成晶片,也称为集成电路,是将数十亿甚至上百亿的微型元件集成到......