#include <bits/stdc++.h>
using namespace std;
struct Node {
int L, R, V;
};
bool check(vector<int> Adj[], int Src,
int N, bool visited[])
{
int color[N] = { 0 };
visited[Src] = true;
queue<int> q;
q.push(Src);
while (!q.empty()) {
int u = q.front();
q.pop();
int Col = color[u];
for (int x : Adj[u]) {
if (visited[x] == true
&& color[x] == Col) {
return false;
}
else if (visited[x] == false) {
visited[x] = true;
q.push(x);
color[x] = 1 - Col;
}
}
}
return true;
}
void addEdge(vector<int> Adj[],
int u, int v)
{
Adj[u].push_back(v);
Adj[v].push_back(u);
}
void isPossible(struct Node Arr[], int N)
{
vector<int> Adj[N];
for (int i = 0; i < N - 1; i++) {
for (int j = i + 1; j < N; j++) {
if (Arr[i].R < Arr[j].L
|| Arr[i].L > Arr[j].R) {
continue;
}
else {
if (Arr[i].V == Arr[j].V) {
addEdge(Adj, i, j);
}
}
}
}
bool visited[N] = { false };
for (int i = 0; i < N; i++) {
if (visited[i] == false
&& Adj[i].size() > 0) {
if (check(Adj, i, N, visited)
== false) {
cout << "No";
return;
}
}
}
cout << "Yes";
}
int main()
{
struct Node arr[] = {
{ 5, 7, 2 }, { 4, 6, 1 },
{ 1, 5, 2 }, { 6, 5, 1 }
};
int N = sizeof(arr) / sizeof(arr[0]);
isPossible(arr, N);
return 0;
}
0 comments:
Post a Comment