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:

yes no yes no

Code:

#include <iostream> #include <vector> #include<utility> using namespace std; const int N = 1e5 + 5; bool error; int col[N]; vector<pair<int, int>> adj[N]; void dfs(int start) { for (auto edge : adj[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++) { adj[i].clear(); col[i] = -1; } while (m--) { int a, b, c; cin >> a >> b >> c; adj[a].push_back(make_pair(b, c)); adj[b].push_back(make_pair(a, 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)

Leave a Comment