Description
Problem: Given an n × m matrix, can it be an incidence matrix of a simple undirected graph G = (V, E) where |V | = n and |E| = m?
Sample Input
The first line of the input contains an integer t (1 ≤ t ≤ 41), the number of test cases. Each test case starts with a line with two integers n (1 ≤ n ≤ 8) and m (0 ≤ m ≤ n(n − 1)/2). Then n lines containing m integers (0’s or 1’s) each follow such that the j-th number on the i-th line is M(i, j).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
3
3 3
1 1 0
0 1 1
1 0 1
3 1
1
1
0
3 3
1 1 0
1 1 1
1 0 0
Sample Output
For each test case print ‘Yes’ if the incidence matrix given in the input can be an incidence matrix of some simple undirected graph, otherwise print ‘No’.
1
2
3
4
Yes
Yes
No
Ideas
Two cases to satisify
- Sum in column can be 2 or 0.
- No two different edges can join same two edge.
(1) condition is simple we just sum over column and check sum. for (2) condition we use set to check if the indices pair have already edge joining them. For that we convert the vertex index to string and append it together. Then we add them to set.
Solution
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
#define sz(a) int((a).size())
#define pb push_back
#define all(c) (c).begin(), (c).end()
#define tr(c, i) for (typeof((c)).begin() i = (c).begin(); i != (c).end(); i++)
#define present(c, x) ((c).find(x) != (c).end())
#define cpresent(c, x) (find(all(c), x) != (c).end())
// Two cases to satisify
// 1. Sum in column can be 2 or 0
// 2. No two different edges can join same two edge.
int main()
{
int t;
cin >> t;
while (t--)
{
int n, m;
cin >> n >> m;
int mat[n][m];
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
cin >> mat[i][j];
}
}
bool flag = true;
set<string> ss;
for (int i = 0; i < m; i++)
{
int sum = 0;
string s = "";
for (int j = 0; j < n; j++)
{
sum += mat[j][i];
if (mat[j][i] != 0)
{
s += ('0' + j);
}
}
//cout << s << endl;
if (sum != 2 || s.length() != 2 || ss.find(s) != ss.end())
{
flag = false;
break;
}
ss.insert(s);
}
if (flag)
cout << "Yes" << endl;
else
cout << "No" << endl;
}
return 0;
}