# Help me with Chef and Friends from Sept long 2016

I can’t understand how the Adjacency matrix and DFS works in this solution code…Please guide me and link resources to learn if possible. Thank you

Problem: Chef and Friends

I think you should have a look at this tutorial if you are not aware of Graph Theory-

Input

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.

The first line of each test case contains two space-separated integers N and M, denoting the number of Chef’s friends and the number of pairs representing information whether two person know each other or not.

The next M lines contain two space-separated integers ai and bi, denoting that persons ai and bi know each other.
################## …
Suppose I enter following as input

1

4 3

1 2

1 3

1 4

###### …

Initially the adj matrix will have values

adj[][] =

{

0 1 1 1

1 0 1 1

1 1 0 1

1 1 1 0
}

Refer This solution

But after this code of 2 lines

for i=0 to i=m

adj[u-1][v-1]=0;

adj[v-1][u-1]=0;

After running above 2 statements the value of adj matrix will be

adj[][] =

{

0 0 0 0

0 0 1 1

0 1 0 1

0 1 1 0
}
Why are we doing these changes to adj matrix? Please help me

Can someone tell me how this piece of code works in this solution?

Thanks.

Solution chef and friends

``````bool ok = 1;
for(int i = 0; i < 2; i++)
for(int j = 0; j < c[i].size(); j++)
for(int k = j + 1; k < c[i].size(); k++)
ok &= a[c[i][j]][c[i][k]];

puts(ok? "YES" : "NO");``````
`````` for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
if(i!=j)
{
adj[i][j]=1;
}
else adj[i][j]=0;
``````

His initial adj matrix is all 1. He is using opposite terminology here. What we denote by 1, he is denoting by 0 and vice versa.