HDU 3478 Catch(二分图判定)
http://acm.hdu.edu.cn/showproblem.php?pid=3478
题意:给你一个N个节点和M条边的无向图,并且给你一个起点X,小偷从起点X出发,每个单位时间只能从一点走到相邻的点上.现在问你有没有一个时刻小偷可能在地图的任意节点上?
分析:
我们称那个符合要求的时刻为:完美时刻.首先如果这个无向图是不连通,就不存在完美时刻. 当无向图连通的时候,如果该图是二分图,依然不存在完美时刻.(想想为什么?) 因为整个图被分为两半,一半是奇数时刻能到的,另一半是偶数时刻能到的.
综上所述,只有在图连通且非二分图的时候,才能保证有完美时刻存在.我们只需要判断图是否连通且非二分图即可.其中图是否连通可以直接通过从起点S对图节点染色后,看看是否还有未染色的节点来得出.(错误,不可通过二分图递归判断,因为如果颜色冲突了就立即返回,其他点都没有染色).
连通必须通过并查集判断.
当然这题也可以用BFS来判断当前图是不是二分图,原理与DFS判断类似,都是通过染色看看是否冲突来判断.
AC代码:
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
const int maxn=100000+10;
const int maxm=500000+10;
int n,m,s;
vector<int> G[maxn];
int color[maxn];
int fa[maxn];
int find(int i)
{
if(fa[i]==-1) return i;
return fa[i]=find(fa[i]);
}
bool bipartite(int u)
{
for(int i=0;i<G[u].size();i++)
{
int v=G[u][i];
if(color[v]==color[u]) return false;
if(color[v]==0)
{
color[v]=3-color[u];
if(!bipartite(v)) return false;
}
}
return true;
}
int main()
{
int T; scanf("%d",&T);
for(int kase=1;kase<=T;kase++)
{
scanf("%d%d%d",&n,&m,&s);
for(int i=0;i<n;i++) G[i].clear();
memset(color,0,sizeof(color));
memset(fa,-1,sizeof(fa));
for(int i=0;i<m;i++)
{
int u,v;
scanf("%d%d",&u,&v);
G[u].push_back(v);
G[v].push_back(u);
u=find(u), v=find(v);
if(u!=v) fa[u]=v;
}
int cnt=0; //连通分量个数
for(int i=0;i<n;i++)if(find(i)==i) cnt++;
if(cnt>1)
{
printf("Case %d: NO\n",kase); //这里忘了Case %d了,WA了
continue;
}
bool sign=true; //存在完美时刻
color[s]=1;
if(bipartite(s)) sign=false;
printf("Case %d: %s\n",kase,sign?"YES":"NO");
}
return 0;
}
分享到:
相关推荐
在给定的题目链接中,例如http://acm.hdu.edu.cn/showproblem.php?pid=1533,这些题目都是关于二分图完美匹配的应用实例,通过KM算法可以高效地找到解决方案。理解并掌握KM算法对于解决这类问题至关重要。
B HDU 5093 Battle ships题意给出一个n行m列的图,*代表海域,o代表冰水,#代表冰山,要想在海域中放置船,保证船与船之间不能相互看到,之间
二分图匹配实例代码及整理 1、匈牙利算法 HDU 1150 #include #include #include using namespace std; int m,n,k; int vis[105]; int mpt[105][105]; int use[105]; int hungary(int x) { for(int i=1;i<m;i++)...
ACM HDU 题目分类 ACM HDU 题目分类是指对 HDU 在线判题系统中题目的分类,总结了大约十来个分类。这些分类将有助于编程选手更好地理解和解决问题。 DP 问题 DP(Dynamic Programming,动态规划)是一种非常重要...
本人准备2020年保研机试时刷的题目(虽然最后机试取消了,...来自某中流985,在HDU和vjudge平台上大概刷了400道。本文件地图(excel表格)包含了绝大部分我刷过的题目,笔记中具有思路、代码、总结和心得。 大佬勿入!
8. **图论与树**:HDU题目中可能涉及图的遍历(深度优先搜索DFS、广度优先搜索BFS)、树的遍历(前序、中序、后序)以及最小生成树、最短路径等算法。 9. **动态规划**:这是一种优化策略,通过构建状态转移方程来...
HDU ACM培训资料是一系列专为参与ACM(国际大学生程序设计竞赛)的学员准备的教育资源,涵盖了算法和编程竞赛的核心知识。这份压缩包包含了11个不同主题的课时,旨在帮助学员全面掌握ACM竞赛所需的技能。下面将详细...
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
【标题】"HDU DP动态规划"涉及到的是在算法领域中的动态规划(Dynamic Programming,简称DP)技术,这是解决复杂问题的一种高效方法,尤其适用于有重叠子问题和最优子结构的问题。动态规划通常用于优化多阶段决策...
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
本分类涵盖了图论领域的多种类型的题目,涉及到图论的基本概念、图的遍历、图的搜索、图的匹配、图的.isConnected性、图的最短路径、图的最小生成树、图的拓扑排序等多个方面。 图论是一个重要的计算机科学领域,...
【ACM HDU】指的是在ACM(国际大学生程序设计竞赛,International Collegiate Programming Contest)中,参赛者在杭州电子科技大学(Hangzhou Dianzi University,简称HDU)的在线评测系统上完成并已解决的题目集合...
2. **数据结构**:常用的数据结构包括数组、链表、栈、队列、树(二叉树、平衡树如AVL和红黑树)、图等,对于不同的问题,选择合适的数据结构能有效提高解题效率。 3. **字符串处理**:杭电ACM中的题目可能涉及到...
hdu2101AC代码
3. **数据结构**:数组、链表、栈、队列、树(二叉树、平衡树如AVL和红黑树)、图(邻接矩阵、邻接表、最小生成树、拓扑排序等)。 4. **字符串处理**:KMP算法、Manacher's Algorithm、Rabin-Karp算法等。 5. **...
搜索 dfs 解题代码 hdu1241
【ACM入门与提高:HDU ACM竞赛课程详解】 ACM(国际大学生程序设计竞赛,International Collegiate Programming Contest,简称ICPC或ACM/ICPC)是一项全球性的竞赛,旨在激发大学生对计算机科学的兴趣,提升他们的...
3. **算法与数据结构**:HDU的题目通常涉及到基础和高级算法,如排序、搜索、图论、动态规划等,以及各种数据结构,如链表、树、堆、图等。通过分析这些源代码,可以学习到如何在实际问题中应用这些理论知识。 4. *...