北京网站开发公司电话,常用的品牌策划公司,网站推广优化公司,山西建设网官方网站本题链接 #xff1a;活动 - AcWing
题目#xff1a;
样例#xff1a; 输入 4 4
1 3
1 4
2 3
2 4 输出 Yes 思路#xff1a; 根据题目意思#xff0c;我们明确一下二分图的含义。 二分图是图论中的一个重要概念。一个图被称为二分图#xff0c;当且仅当能够将其所有顶…本题链接 活动 - AcWing
题目
样例
输入 4 4
1 3
1 4
2 3
2 4 输出 Yes 思路 根据题目意思我们明确一下二分图的含义。 二分图是图论中的一个重要概念。一个图被称为二分图当且仅当能够将其所有顶点分割成两个互不相交的子集使得每条边的两个顶点分别属于不同的子集。 换句话说对于一个二分图可以把图中的顶点分成两组使得同一组内的顶点之间没有边相连而不同组内的顶点之间有边相连。 通俗的讲二分图就像是一个人群中的男女混合舞会所有参与者可以分成两组男生和女生。在这个舞会上男生只和女生跳舞而不和其他男生跳舞女生也只和男生跳舞而不和其他女生跳舞。没有两个男生或两个女生会成对跳舞。 如果一个图是二分图就意味着可以将所有的点分成两组使得同一组内的点之间没有直接相连的边而不同组内的点之间有直接相连的边。这种特性在很多实际问题中都有重要的应用。 所以我们可以用DFS或者BFS暴搜即可枚举出答案。
代码详解如下
DFS法
#include iostream
#include vector
#include queue
#include cstring
#include algorithm
#include unordered_map
#define endl \n
#define int long long
#define Yes puts(Yes)
#define No puts(No)
#define umap unordered_map
#define All(x) x.begin(),x.end()
#pragma GCC optimize(3,Ofast,inline)
#define IOS std::ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)
using namespace std;
const int N 2e6 10;int n,m;// 数组模拟链表
vectorinth(N,-1); // 链表头指针
int e[N],ne[N],idx;
inline void Add(int a,int b)
{e[idx] b,ne[idx] h[a],h[a] idx;
}int color[N]; // 记录是否染色
// color 状态 0 表示未染色
// 1 表示染黑色
// 2 表示染白色bool DFS(int node,int inColor)
{color[node] inColor; // 将其染色// 枚举其相连的结点查看是否染色for(int i h[node];i ! -1;i ne[i]){int j e[i]; // 取出相邻的结点// 如果相邻的结点没有染色if(!color[j]){// 我们将其染成当前结点的另一种颜色,其中如果出现冲突的染色我们返回 falseif(!DFS(j,3 - inColor)) return false;}else if(inColor color[j]) return false;// 否则如果相邻的结点已经染色了并且出现与当前结点的颜色冲突我们返回 false}return true; // 染色没有问题返回 true
}inline void solve()
{cin n m;while(m--){int a,b;cin a b;Add(a,b),Add(b,a); // 由于是无向图所以双向相连}// 枚举每个结点查看是否染色for(int i 1;i n;i){// 如果没有染色那么我们将其染色if(!color[i]){// 如果出现冲突的染色,直接输出 Noif(!DFS(i,1)){No;return ;}}}Yes; // 如果都符合二分图定义输出 Yes
}signed main()
{
// freopen(a.txt, r, stdin);IOS;int _t 1;
// cin _t;while (_t--){solve();}return 0;
}
最后提交
BFS法
#include iostream
#include vector
#include queue
#include cstring
#include algorithm
#include unordered_map
#define endl \n
#define int long long
#define Yes puts(Yes)
#define No puts(No)
#define umap unordered_map
#define All(x) x.begin(),x.end()
#pragma GCC optimize(3,Ofast,inline)
#define IOS std::ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)
using namespace std;
const int N 2e6 10;
using PIIpairint,int;
int n,m;// 数组模拟链表
vectorinth(N,-1); // 链表头指针
int e[N],ne[N],idx;
inline void Add(int a,int b)
{e[idx] b,ne[idx] h[a],h[a] idx;
}int color[N]; // 记录是否染色
// color 状态 0 表示未染色
// 1 表示染黑色
// 2 表示染白色inline bool BFS()
{queuePIIq; // 存储需染色结点// 枚举每个结点for(int i 1;i n;i){if(!color[i]){q.emplace(PII(i,1));// BFS 搜索while(q.size()){// 取出需染色的结点PII now q.front(); q.pop();// 获取数据int node now.first;int inColor now.second;color[node] inColor; // 开始染色// 枚举相邻的结点,是否染色for(int i h[node];i ! -1;i ne[i]){int j e[i];if(!color[j]){q.emplace(PII(j,3 - inColor)); // 存储染色结点}else if(color[j] inColor) return false;}}}}return true;
}inline void solve()
{cin n m;while(m--){int a,b;cin a b;Add(a,b),Add(b,a); // 由于是无向图所以双向相连}if(BFS()) Yes;else No;
}signed main()
{
// freopen(a.txt, r, stdin);IOS;int _t 1;
// cin _t;while (_t--){solve();}return 0;
}
最后提交
