Help me with Chef and Friends from Sept long 2016

help
,
1

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

2

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

3

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

4 
 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.

5

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");