Find minimum number of people to reach to spread a message across all people in twitter


  • 14
    I

    Considering that I'ld would like to spread a promotion message across all people in twitter. Assuming the ideal case, if a person tweets a message, then every follower will re-tweet the message.

    You need to find the minimum number of people to reach out (for example, who doesn't follow anyone etc) so that your promotion message is spread out across entire network in twitter.

    Also, we need to consider loops like, if A follows B, B follows C, C follows D, D follows A (A -> B -> C -> D -> A) then reaching only one of them is sufficient to spread your message.

    Input: A 2x2 matrix like below. In this case, a follows b, b follows c, c follows a.

        a b c
    a  1 1 0
    b  0 1 1
    c  1 0 1
    

    Output: List of people to be reached to spread out message across everyone in the network.


  • 39

    This is a very interesting graph problem, here is what I would do:

    step 1. Build a directed graph based on the input people (nodes) and their relationship (edges).

    step 2. Find strongly connected components (SCCs) in the graph. Let's use the wikipedia's graph example, in that case, there are 3 SCCs: (a, b, e), (c, d, h) and (f, g). There are two famous algorithms for getting the SCCs: Kosaraju's algorithm and Tarjan's algorithm.

    step 3. Pick one of the nodes from the SCCs we get: a, c, f, now these 3 nodes form a DAG, we just need to do topological sort for them, eventually a is the root node in the path (or stack), and we can let a spread the message and guarantee all other people will get it.

    Sometimes, there could be several topological paths, and the root nodes of those paths will be the minimum people to reach out to spread the message.


  • 1
    J

    I don't know whether I am over simplifying the problem but my humble observation is as follows:

    1. There is an edge from a to b iff b follows a. (this represent the information flow)
    2. If we systematically perform BFS on every not visited node, we can safely delete every unvisited node we discover except the root since these discovered nodes doesn't contribute to the answer.
    3. In the end simply print the nodes not deleted. They are the minimum set of people to reach.

  • 5

    For each unvisited node, add it to the sender list and search all nodes including visited nodes starting from it, mark unvisited nodes as visited, if a sender is seen, remove it from the sender list.
    O(n^2)
    I think it is a good problem to add to oj.


  • 0
    A
    This post is deleted!

  • 3
    A

    @jeantimex Why strongly connected components only? You could have A->B->C which doesn't form a "strongly connected" component. I would imagine a "connected" component works better for this case.

    In case there truly weren't cycles, which isn't explicitly stated int the question, we could use topological sorting.
    Step3 would then have to account for the fact that after topological sorting is done, we might end up with multiple root nodes per connected component. Gathering all these root nodes up we'll have a final set and consequent count.


  • 1
    L

  • 0
    This post is deleted!

  • 0
    T
    This post is deleted!

  • 0
    N

    This is a very interesting graph problem


  • 0
    A

    Is this problem an instance of the Dominating Set problem in graph theory?


  • 0
    A

    Just wondering why can't we use simple UnionFind here to find the number of connected components? Am I missing something?


  • 1
    M

    @amsinha
    In this problem the edges are directed. A following B doesnt imply B follows A.


  • 0
    R

    @amsinha That is only valid if the graph is undirected.


  • 0
    T

    @jeantimex Why does it need to be Strongly connected? For SCC the requirement is more. You need to be able to get to all other nodes from every node. But I think for this problem all we need is just one node from which all other nodes can be reached.

    So finding SCCs sounds like sub-optimal (and hence not correct solutions).

    Any comment?

    Thanks.


  • 0
    
    
    @jeantimex- I came up with this solution based on your insight.
    public List<Integer> minFollowers(int[][] m){
    	List<Integer>[] adj = (ArrayList<Integer>[]) new ArrayList[m.length];
    	for(int i = 0; i < adj.length; i++){
    		adj[i] = new ArrayList<Integer>();
    	}
    	for(int r = 0; r < m.length; r++){
    		for(int c = 0; c < m[0].length; c++){
    			if(r != c && m[r][c] == 1){
    				adj[r].add(c);
    			}
    		}
    	}
    	
    	int[] ds = new int[m.length];
    	for(int i = 0; i < ds.length; i++){
    		ds[i] = i;
    	}
    	boolean[] visited = new boolean[m.length];
    	List<Integer> minFollowers = new ArrayList<Integer>();
    	for(Integer x: adj[0]){//Assuming 0 is the origin (starting person). Iterate through his unvisited friends and use DFS
    							//to identify connected components.
    		if(!visited[x]){
    			minFollowers.add(x);
    			dfs(visited,x,ds,adj);
    		}
    	}
    	return minFollowers;
    }
    
    private void dfs(boolean[] b, int vtx, int[] ds, List<Integer>[] adj){
    	b[vtx] = true;
    	for(Integer x: adj[vtx]){
    		if(!b[x]){
    			int p1 = find(x,ds);
    			int p2 = find(vtx,ds);
    			if(p1 != p2){
    				ds[p1] = p2;
    			}
    		
    		}
    	}
    }
    
    private int find(int vtx,int[] ds){
    	if(ds[vtx] == vtx){
    		return vtx;
    	}
    	int ret = find(ds[vtx],ds);
    	ds[vtx] = ret;
    	return ret;
    }

  • 0
    W

    @jeantimex For step 3, after we build a DAG, we just need to count the number of nodes that have zero in-degree.


  • 0
    K

    @divyam01986
    in dfs, there should be no visited check. This prevents visited connected components to be added to the unvisited one.


  • 1
    L

    @arxoclay SCC is only the first step to eliminate nodes in a cycle. After that a topological sort is deployed to find the left needed nodes. In your case (A->B->C), since there is no SCC, then the algorithm will go to step to directly, and do the topological sort on it and figure out only A is needed to inform.


  • 0
    W

    @jeantimex Can we just delete all nodes with more than 0 incoming edges and print the ones left, plus one node from each cycle as the final answer?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.