本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】洛谷P1330 封锁阳光大学 - 洛谷【题目描述】曹是一只爱刷街的老曹暑假期间他每天都欢快地在阳光大学的校园里刷街。河蟹看到欢快的曹感到不爽。河蟹决定封锁阳光大学不让曹刷街。阳光大学的校园是一张由n nn个点构成的无向图n nn个点之间由m mm条道路连接。每只河蟹可以对一个点进行封锁当某个点被封锁后与这个点相连的道路就被封锁了曹就无法在这些道路上刷街了。非常悲剧的一点是河蟹是一种不和谐的生物当两只河蟹封锁了相邻的两个点时他们会发生冲突。询问最少需要多少只河蟹可以封锁所有道路并且不发生冲突。【输入】第一行两个正整数n , m n,mn,m表示节点数和边数。接下来m mm行每行两个整数u , v u,vu,v表示点u uu到点v vv之间有道路相连。【输出】仅一行如果河蟹无法封锁所有道路则输出Impossible否则输出一个整数表示最少需要多少只河蟹。【输入样例】3 3 1 2 1 3 2 3【输出样例】Impossible【算法标签】#普及 #二分图【代码详解】#includebits/stdc.husingnamespacestd;constintN10005,M100005*2;intn,m,ans;// n: 点数m: 边数ans: 最少需要放置的河蟹数量inth[N],e[M],ne[M],idx;// 邻接表intcolor[N];// 染色数组0表示未染色1表示第一种颜色2表示第二种颜色intcnt[3];// 记录每个连通块中两种颜色的数量intd[N];// 记录每个点的度数voidadd(inta,intb)// 添加无向边{e[idx]b,ne[idx]h[a],h[a]idx;d[a];// 增加点的度数}booldfs(intu,intc)// 深度优先搜索判断是否为二分图{color[u]c;// 染色cnt[c];// 对应颜色的计数加1for(intih[u];i!-1;ine[i])// 遍历邻居{intve[i];if(color[v]0)// 如果邻居未染色{if(dfs(v,3-c)false)// 递归染色returnfalse;}elseif(color[v]c)// 如果邻居颜色相同{returnfalse;// 不是二分图}}returntrue;// 是二分图}intmain(){cinnm;// 输入点数和边数memset(h,-1,sizeof(h));// 初始化邻接表while(m--)// 输入每条边{intu,v;cinuv;add(u,v);add(v,u);}boolflagtrue;// 标记是否为二分图for(inti1;in;i)// 遍历每个点{if(color[i]0)// 如果未染色{// 孤立点不需要河蟹if(d[i]0)// 如果是孤立点continue;// 跳过cnt[1]cnt[2]0;// 重置计数器if(dfs(i,1)false)// 如果不是二分图{flagfalse;// 标记为不是二分图break;// 退出循环}ansmin(cnt[1],cnt[2]);// 累加最少需要的河蟹数量}}if(!flag)// 如果不是二分图coutImpossibleendl;// 输出不可能elsecoutansendl;// 输出最少需要的河蟹数量return0;}【运行结果】3 3 1 2 1 3 2 3 Impossible
题解：洛谷 P1330 封锁阳光大学
发布时间：2026/6/3 10:03:30
本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】洛谷P1330 封锁阳光大学 - 洛谷【题目描述】曹是一只爱刷街的老曹暑假期间他每天都欢快地在阳光大学的校园里刷街。河蟹看到欢快的曹感到不爽。河蟹决定封锁阳光大学不让曹刷街。阳光大学的校园是一张由n nn个点构成的无向图n nn个点之间由m mm条道路连接。每只河蟹可以对一个点进行封锁当某个点被封锁后与这个点相连的道路就被封锁了曹就无法在这些道路上刷街了。非常悲剧的一点是河蟹是一种不和谐的生物当两只河蟹封锁了相邻的两个点时他们会发生冲突。询问最少需要多少只河蟹可以封锁所有道路并且不发生冲突。【输入】第一行两个正整数n , m n,mn,m表示节点数和边数。接下来m mm行每行两个整数u , v u,vu,v表示点u uu到点v vv之间有道路相连。【输出】仅一行如果河蟹无法封锁所有道路则输出Impossible否则输出一个整数表示最少需要多少只河蟹。【输入样例】3 3 1 2 1 3 2 3【输出样例】Impossible【算法标签】#普及 #二分图【代码详解】#includebits/stdc.husingnamespacestd;constintN10005,M100005*2;intn,m,ans;// n: 点数m: 边数ans: 最少需要放置的河蟹数量inth[N],e[M],ne[M],idx;// 邻接表intcolor[N];// 染色数组0表示未染色1表示第一种颜色2表示第二种颜色intcnt[3];// 记录每个连通块中两种颜色的数量intd[N];// 记录每个点的度数voidadd(inta,intb)// 添加无向边{e[idx]b,ne[idx]h[a],h[a]idx;d[a];// 增加点的度数}booldfs(intu,intc)// 深度优先搜索判断是否为二分图{color[u]c;// 染色cnt[c];// 对应颜色的计数加1for(intih[u];i!-1;ine[i])// 遍历邻居{intve[i];if(color[v]0)// 如果邻居未染色{if(dfs(v,3-c)false)// 递归染色returnfalse;}elseif(color[v]c)// 如果邻居颜色相同{returnfalse;// 不是二分图}}returntrue;// 是二分图}intmain(){cinnm;// 输入点数和边数memset(h,-1,sizeof(h));// 初始化邻接表while(m--)// 输入每条边{intu,v;cinuv;add(u,v);add(v,u);}boolflagtrue;// 标记是否为二分图for(inti1;in;i)// 遍历每个点{if(color[i]0)// 如果未染色{// 孤立点不需要河蟹if(d[i]0)// 如果是孤立点continue;// 跳过cnt[1]cnt[2]0;// 重置计数器if(dfs(i,1)false)// 如果不是二分图{flagfalse;// 标记为不是二分图break;// 退出循环}ansmin(cnt[1],cnt[2]);// 累加最少需要的河蟹数量}}if(!flag)// 如果不是二分图coutImpossibleendl;// 输出不可能elsecoutansendl;// 输出最少需要的河蟹数量return0;}【运行结果】3 3 1 2 1 3 2 3 Impossible
