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 asked 09 Aug '17, 14:21
converted to question 09 Aug '17, 14:55

I think you should have a look at this tutorial if you are not aware of Graph Theory https://www.hackerearth.com/practice/algorithms/graphs/graphrepresentation/tutorial/ answered 09 Aug '17, 14:56

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 spaceseparated 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 spaceseparated 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[u1][v1]=0; adj[v1][u1]=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 answered 09 Aug '17, 20:34

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 spaceseparated 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 spaceseparated 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[u1][v1]=0; adj[v1][u1]=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 answered 09 Aug '17, 20:35
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.
(09 Aug '17, 23:42)

Can someone tell me how this piece of code works in this solution? Thanks.
answered 12 Aug '17, 18:36
