SNET - Editorial ( NCC 2014 )

editorial
, , , ,
1

PROBLEM LINK:

Contest

Practice

Author: Vaibhav Tulsyan, Aditya Sarode

Tester: Aditya Sarode

Editorialist: Aditya Sarode

DIFFICULTY:

MEDIUM

PREREQUISITES:

Graphs, DFS

PROBLEM:

Given a graph with K edges, find out the number of nodes connected to Mr. X such that the friend has the largest network of friends.

QUICK EXPLANATION:

Construct graph using adjacency lists, sort the adjacency lists lexicographically, apply DFS to find the sizes of subgraphs connected to Mr. X.

EXPLANATION:

We construct a graph in which the people are nodes and an edge between two nodes represent that the two people are friends.

So the problem is reduced to, given an undirected graph find out the number of nodes of a friend of Mr. X such that the friend has the largest network of friends.

To find the number of people in the network of a friend of Mr. X, we can apply dfs on that particular friend. The dfs would return the number of people in it’s network.

But applying Dfs seperately on each of Mr. X’s friend can result in a TLE, given the limits.

Thus we sort the adjacency list of Mr. X and apply dfs and as we are traversing each node, we mark it as visited. While applying dfs for other friends, we don’t consider them who have already been marked visited.

If two friends of Mr. X are in the same network, initially the one with lexicographically smallest name will be visited and so DFS won’t be applied to the next friend. Both the friends will have the same number of friends in network, but we need to consider the lexicographically smallest, which is achieved by applying DFS in this manner.

The number of nodes are not given, so the nodes must be added dynamically.

1 Like
2

i’m a beginner…i have just learnt the dfs algorithm…can anyone plz plz plzz explain how to create the adjecency matrix from the given input of this problem…and how to solve this without getting TLE in detail…thanks in advance.

3

@trek:

Creating adjacency matrix/list:

You can map the strings to integers first and then create an adjacency matrix in the usual way.

For example, if the input is of the form:

A B

A C

C D

C E

Then we know that there are 5 distinct vertices, viz. A, B, C, D, E.

We can create a map - { A: 1, B: 2, C: 3, … }

Now, to create the adjacency matrix, just use these integral values and proceed.

Solving the problem:

You just need to sort the adjacency list of X, i.e. the person who is going to the post, and then apply DFS.

1 Like
4

thank you !!!

5

can u plz post ur solution in c so that i can understand it completely…!!plz

6

Here’s our solution in C++ - http://ideone.com/I4dvAF

1 Like