CCC '09 S3 - Degrees Of Separation

View as PDF
Submit solution
Points: 10
Time limit: 1.0s
Memory limit: 256M
Problem type
Canadian Computing Competition: 2009 Stage 1, Junior #5, Senior #3

The main socializing tool for students today is Facebook. There are many interesting computational questions connected to Facebook, such as the "degree of separation" between two people.

For example, in the diagram below, there are many different paths between Abby and Alberto. Some of these paths are:

  • Abby → Zoey → Alberto
  • Abby → Natalie → Zoey → Alberto
  • Abby → George → Ali → Kara → Richardo → Jeff → Alberto

The shortest path between Abby and Alberto has two steps (Abby → Zoey, and Zoey → Alberto), so we say the degree of separation is 2. Additionally, Alberto would be a friend of a friend of Abby.

You can assume an initial configuration of who is friends with who as outlined in the diagram above. You will need to store these relationships in your program. These relationships can change though, and your program needs to handle these changes. In particular, friendships can begin, possibly with new people. Friendships can end. You should be able to find friends of friends and determine the degree of separation between two people.

Input/Output Description

Your program will read in six possible commands, with the action to be performed by your program outlined below. You may assume that x and y are integers, with x \ne y, x \ge 1, y \ge 1, x < 50 and y < 50. You may also assume that instructions (i, d, n, f, s, q) occur one per line and parameters (zero, one or two integers) occur one per line.

  • i x y - make person x and person y friends. If they are already friends, no change needs to be made. If either x or y is a new person, add them.
  • d x y - delete the friendship between person x and person y.
  • n x - output the number of friends that person x has.
  • f x - output the number of "friends of friends" that person x has. Notice that x and direct friends of x are not counted as "friends of friends."
  • s x y - output the degree of separation between x and y. If there is no path from x to y, output Not connected.
  • q - quit the program.

Sample Input

i
20
10
i
20
9
n
20
f
20
s
20
6
q

Sample Output

2
3
4

Explanation

  • n 20: Person 20 has two friends (10 and 9).
  • f 20: The friends of friends of 20 are 8, 11, 12.
  • s 20 6: The shortest path is 20 → 9 → 8 → 7 → 6.

Comments


  • 1
    stampixel  commented on Jan. 13, 2023, 10:04 p.m. ← edited

    Anyone know why mine works for the test case and not the actual judge cases?

    Edit: Solved, something was wrong with my "f" case, but i figured it out.


  • 5
    planT_444  commented on Jan. 1, 2022, 7:52 p.m.

    the hardest part of the problem is copying down the edges. no, i didn't check the comments before starting because i didn't want to get any clues


  • 1
    yunz_qiao  commented on Oct. 16, 2021, 8:57 p.m.

    any one can please take a look at my submission, where is the point of the last test case, thanks


    • 1
      Antt  commented on Oct. 17, 2021, 3:35 p.m.

      consider the case where they ask you for the degrees of separation between two friends but one of the friends was never introduced


      • 1
        yunz_qiao  commented on Oct. 17, 2021, 5:56 p.m.

        Should it not considered as not connected domain? I have that thought, if a new firends node value is 0, then is not coneencted then


  • 10
    Tommy_Shan  commented on Oct. 3, 2021, 7:24 p.m. ← edit 4

    To the people use Python:

    friend = [[],[6],[6],[4,5,6,15],[3,5,6],[3,4,6],[1,2,3,4,5,7],[6,8],[7,9],[8,10,12],[9,11],[10,12],[9,11,13],[12,14,15],[13],[3,13],[17,18],[16,18],[16,17],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[]]

    • -2
      planT_444  commented on Jan. 1, 2022, 7:54 p.m. ← edited

      I used sets for my adjacency matrix. Is it still a matrix if it's sets?


  • 9
    kevze  commented on June 17, 2020, 9:22 p.m. ← edited

    I think the test data is incomplete for this problem.

    https://dmoj.ca/submission/2157288 this passes with AC but fails input f 10

    output is 3 but it should be 2 (double counts friend 12)

    Edit: another example is f 11, again output should be 2 but it passes with output 3


  • 29
    Ibby  commented on June 1, 2020, 11:48 p.m. ← edit 2

    Adjacency list:

    {{}, {6}, {6}, {4,5,6,15}, {3,5,6}, {3,4,6}, {1,2,3,4,5,7}, {6,8}, {7,9}, {8,10,12}, {9,11}, {10,12}, {9,11,13}, {12,14,15}, {13}, {3,13}, {17,18}, {16,18}, {16,17}};


    • 1
      justinjiang37  commented on Aug. 9, 2021, 12:20 a.m.

      dumb ass me was gonna use a map, then I realized that the numbers are all ascending ints...


    • 4
      nathancoulas2003  commented on June 2, 2020, 2:06 a.m.

      spoiler alert


  • 1
    corgi  commented on March 9, 2020, 1:13 a.m. ← edited

    For anyone who doesn't want to type it (just create a function that adds a bidirectional edge): edge(1, 6);edge(2, 6);edge(3, 6);edge(4, 6);edge(5, 6); edge(3, 5);edge(3, 4);edge(4, 5);edge(6, 7);edge(7, 8); edge(8, 9);edge(9, 12);edge(9, 10);edge(10, 11); edge(11, 12);edge(3, 15);edge(12, 13);edge(13, 15); edge(13, 14);edge(16, 18);edge(16, 17);edge(17, 18);


  • 29
    EdwinSun  commented on Sept. 24, 2019, 1:03 p.m. ← edit 3

    For java users (graph):

    adj[1].add(6);adj[2].add(6);adj[3].add(4);adj[3].add(5);adj[3].add(6);
adj[3].add(15);adj[4].add(3);adj[4].add(5);adj[4].add(6);adj[5].add(3);
adj[5].add(3);adj[5].add(4);adj[5].add(6);adj[6].add(1);adj[6].add(2);
adj[6].add(3);adj[6].add(4);adj[6].add(5);adj[6].add(7);adj[7].add(6);
adj[7].add(8);adj[8].add(7);adj[8].add(9);adj[9].add(8);adj[9].add(10);
adj[9].add(12);adj[10].add(9);adj[10].add(11);adj[11].add(10);
adj[11].add(12);adj[12].add(9);adj[12].add(11);adj[12].add(13);
adj[13].add(12);adj[13].add(14);adj[13].add(15);adj[14].add(13);
adj[15].add(3);adj[15].add(13);adj[16].add(17);adj[16].add(18);
adj[17].add(16);adj[17].add(18);adj[18].add(16);adj[18].add(17);

  • 11
    solid_pc31  commented on Aug. 19, 2019, 9:24 p.m. ← edit 2

    for anyone who doesn't want to work out the graph(py3):

    graph={
    1: [6],
    2: [6],
    3: [4, 5, 6, 15],
    4: [3, 5, 6],
    5: [3, 4, 6],
    6: [1, 2, 3, 4, 5, 7],
    7: [6, 8],
    8: [7, 9],
    9: [8, 10, 12],
    10: [9, 11],
    11: [10, 12],
    12: [9, 11, 13],
    13: [12, 14, 15],
    14: [13],
    15:[3,13],
    16:[17,18],
    17:[16,18],
    18:[16,17],
}

    • 4
      Tzak  commented on Aug. 19, 2019, 10:46 p.m. ← edited

      Adjacency list with braces:

      {{}, {6}, {6}, {4, 5, 6, 15}, {3, 5, 6}, {3, 4, 6}, {1, 2, 3, 4, 5, 7}, {6, 8}, {7, 9}, {8, 10, 12}, {9, 11}, {10, 12}, {9, 11, 13}, {12, 14, 15}, {13}, {3, 13}, {17, 18}, {16, 18}, {16, 17}}

  • -1
    echofox  commented on March 20, 2018, 1:24 p.m. ← edited

    can friends of friends overlap


    • 0
      Chris_Xie  commented on March 20, 2018, 6:54 p.m. ← edited

      No. In the diagram given, 10 only has 2 friends of friends: 8 and 12. 12 is not counted twice.


  • -2
    OOOIII  commented on Feb. 7, 2018, 11:44 p.m. ← edited

    You may also assume that instructions (i, d, n, f, s, q) occur one per line and parameters (zero, one or two integers) occur one per line. so it should take in "i 20 10" instead of "i /n 20 /n 10"


  • -1
    Roronoa_Zoro1540  commented on Dec. 21, 2017, 2:13 p.m. ← edited

    can someone check my code to see if I did something wrong or made a stupid mistake?


    • 4
      jkguipqnjcy49979693  commented on Dec. 21, 2017, 2:47 p.m. ← edit 2

      I could be wrong but your Degree of Separation code shouldn't work...

      A counterexample is probably most helpful.

      Consider a graph with the following edges:

      1 2
1 5
2 3
3 4
4 5

      Now when asked to find the shortest path between 1 and 5 (the degree of separation), your algorithm would choose 1->2->3->4->5 even though an edge exists between 1 and 5 directly.

      Punchline is that a DFS can be used to check if a path exists between two vertices, but it does not necessarrily find the shortest such path.

      Probably a good idea would be to google "Depth First Search", "Breadth First Search" etc.

      Again I haven't actually checked your code by running it (cannot right now), so I might be wrong.


  • 1
    aeternalis1  commented on Aug. 3, 2017, 3:32 a.m. ← edit 2

    Oops mb i did not read the question correctly. I thought the diagram was just an example of how connections worked.


  • 1
    Anix55  commented on Feb. 18, 2016, 1:02 a.m. ← edit 6

    can anyone explain this friends of friends thing


    • -3
      minecraftyugi  commented on Feb. 18, 2016, 9:43 p.m. ← edited

      For every friend that a person has, count the total number of friends that that friend has, excluding the original person and the person's direct friends.


  • 5
    FluffyPanda  commented on Jan. 14, 2016, 9:03 p.m. ← edited

    This problem is also an S3, not just a J5.