×

# Help me with Chef and Friends from Sept long 2016

 0 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 1 accept rate: 0% 13.8k●1●11●38

 0 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/graph-representation/tutorial/ answered 09 Aug '17, 14:56 13.8k●1●11●38 accept rate: 19%

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

{

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

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

{

0 0 0 0

0 0 1 1

0 1 0 1

1
accept rate: 0%

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

{

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

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

{

0 0 0 0

0 0 1 1

0 1 0 1

1
accept rate: 0%

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.

(09 Aug '17, 23:42)
 0 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");  answered 12 Aug '17, 18:36 1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×2,376
×85

question asked: 09 Aug '17, 14:21

question was seen: 289 times

last updated: 12 Aug '17, 18:36