AcWing 860. 染色法判定二分图
原题链接
简单
作者:
芝居気
,
2021-12-05 19:29:57
,
所有人可见
,
阅读 129
#include<iostream>
#include<map>
#include<unordered_map>
#include<vector>
#include<queue>
#include<stdio.h>
using namespace std;
unordered_map<int, vector<int>> mp;
void add(int a, int b)
{
mp[a].push_back(b);
}
const int N = 100005;
int st[N];
int n, m;
int p[N];
int find(int x)
{
if (x != p[x]) return p[x] = find(p[x]);
return p[x];
}
int bfs()
{
queue<int> q;
for (int i = 1; i <= n; i++)
{
int u = find(i);
if (!st[u])//i的祖先,即i所属的联通块入列,若该联通块已在队列中,则跳过
{
q.push(u);
st[u] = 1;
}
}
while (!q.empty())
{
int temp = q.front();
q.pop();
for (int i : mp[temp])
{
if (st[i] == st[temp])
{
return 0;
}
else if (st[i] == 0)
{
q.push(i);
st[i] = st[temp] * -1;
}
}
}
return 1;
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
p[i] = i;
for (int i = 0; i < m; i++)
{
int a, b;
cin >> a >> b;
//if (a == b)continue;
add(a, b);
add(b, a);
if (find(a) != find(b))
p[find(a)] = find(b);
}
if (bfs() == 0)cout << "No" << endl;
else cout << "Yes" << endl;
}