You are not logged in. Please login at www.codechef.com to post your questions!

×

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

asked 09 Aug, 14:21

newatschool's gravatar image

0★newatschool
1
accept rate: 0%

converted to question 09 Aug, 14:55

vijju123's gravatar image

4★vijju123
7.4k212


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/

link

answered 09 Aug, 14:56

vijju123's gravatar image

4★vijju123
7.4k212
accept rate: 17%

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

link

answered 09 Aug, 20:35

newatschool's gravatar image

0★newatschool
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, 23:42) vijju1234★

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

answered 12 Aug, 18:36

newatschool's gravatar image

0★newatschool
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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:

×1,557
×73

question asked: 09 Aug, 14:21

question was seen: 115 times

last updated: 12 Aug, 18:36