CPP Program Fill The Matrix – Advanced Graphs

• A matrix B (consisting of integers) of dimension N × N is said to be good if there exists an array A (consisting of integers) such that B[i][j] = |A[i] – A[j]|, where |x| denotes absolute value of integer x.
• You are given a partially filled matrix B of dimension N × N. Q of the entries of this matrix is filled by either 0 or 1. You have to identify whether it is possible to fill the remaining entries of matrix B (the entries can be filled by any integer, not necessarily by 0 or 1) such that the resulting fully filled matrix B is good.

Input

• The first line of the input contains an integer T denoting the number of test cases.
• The first line of each test case contains two space-separated integers N, and Q.
• Each of the next Q lines contains three space-separated integers i, j, Val, which means that B[i][j] is filled with value val.

Output

For each test case, output “yes” or “no” (without quotes) in a single line corresponding to the answer to the problem.

Constraints

1 ≤ T ≤ 10^6
2 ≤ N ≤ 10^5
1 ≤ Q ≤ 10^6
1 ≤ i, j ≤ N
0 ≤ val ≤ 1
The Sum of each of N, and Q over all test cases doesn’t exceed 106

Sample Input 3:

```4
2 2
1 1 0
1 2 1
2 3
1 1 0
1 2 1
2 1 0
3 2
2 2 0
2 3 1
3 3
1 2 1
2 3 1
1 3 1```

Sample Output 3:

```.wp-block-code {
border: 0;
}

.wp-block-code > span {
display: block;
overflow: auto;
}

.shcb-language {
border: 0;
clip: rect(1px, 1px, 1px, 1px);
-webkit-clip-path: inset(50%);
clip-path: inset(50%);
height: 1px;
margin: -1px;
overflow: hidden;
position: absolute;
width: 1px;
word-wrap: normal;
word-break: normal;
}

.hljs {
box-sizing: border-box;
}

.hljs.shcb-code-table {
display: table;
width: 100%;
}

.hljs.shcb-code-table > .shcb-loc {
color: inherit;
display: table-row;
width: 100%;
}

.hljs.shcb-code-table .shcb-loc > span {
display: table-cell;
}

.wp-block-code code.hljs:not(.shcb-wrap-lines) {
white-space: pre;
}

.wp-block-code code.hljs.shcb-wrap-lines {
white-space: pre-wrap;
}

.hljs.shcb-line-numbers {
border-spacing: 0;
counter-reset: line;
}

.hljs.shcb-line-numbers > .shcb-loc {
counter-increment: line;
}

.hljs.shcb-line-numbers .shcb-loc > span {
}

.hljs.shcb-line-numbers .shcb-loc::before {
border-right: 1px solid #ddd;
content: counter(line);
display: table-cell;
text-align: right;
-webkit-user-select: none;
-moz-user-select: none;
-ms-user-select: none;
user-select: none;
white-space: nowrap;
width: 1%;
}
```yes
no
yes
no ``````

Code:

``````#include <iostream>
#include <vector>
#include<utility>
using namespace std;

const int N = 1e5 + 5;
bool error;
int col[N];

void dfs(int start)
{
{
int next = edge.first;
if (col[next] == -1)
{
col[next] = col[start] ^ edge.second;
dfs(next);
}
else if (col[next] != col[start] ^ edge.second)
{
error = true;
}
}
}

int main()
{
int t;
cin >> t;
while (t--)
{
int n, m;
cin >> n >> m;
error = false;
for (int i = 1; i <= n; i++)
{
col[i] = -1;
}
while (m--)
{
int a, b, c;
cin >> a >> b >> c;
}
for (int i = 1; i <= n; i++)
{
if (col[i] == -1)
{
col[i] = 0;
dfs(i);
}
}
if (error)
cout << "no" << endl;
else
cout << "yes" << endl;
}
}
```Code language: C++ (cpp)```