LintCode: Social Network

Social Network



Similar Problems:


Description

Everyone has their online friends. Now there are n people and m friend relationships . Ask if any person can directly or indirectly contact all online people. If ok, return “yes”, else return “no”.
The friend relationship is represented by a array a and a array b, which means that a[i] and b[i] are a pair of friends.

  • 1 <= n <= 5000
  • 1 <= m <= 10000

A person may be friends with himself

Example

Given n=4, a=[1,1,1], b=[2,3,4],return yes.


1 and 2, 3, 4 can be directly contacted
2, 3, 4 and 1 can be directly contacted, these 3 people can be indirectly contacted by 1

Given n=5, a=[1,2,4], b=[2,3,5], return no.

1,2,3 can be connected to each other
4,5 can communicate with each other
However, the two groups cannot be contacted. For example, 1 cannot contact 4 or 5

Github: code.dennyzhang.com

Credits To: lintcode.com

Leave me comments, if you have better ways to solve.


  • Solution:
// Blog link: https://code.dennyzhang.com/social-network
// Basic Ideas: BFS
// Check whether graph is one connected graph
//
// Complexity: Time O(n), Space O(n)
/**
 * @param n: the person sum
 * @param a: the array a
 * @param b: the array b
 * @return: yes or no
 */
func socialNetwork (n int, a []int, b []int) string {
    if n == 0 { return "no" }

    m := map[int][]int{}
    visited := make([]bool, n)
    for i, _ := range a {
        n1, n2 := a[i]-1, b[i]-1
        m[n1] = append(m[n1], n2)
        m[n2] = append(m[n2], n1)
    }

    queue := []int{0}
    visited[0] = true
    for len(queue) != 0 {
        l := []int{}
        for _, node := range queue {
            for _, node2 := range m[node] {
                if !visited[node2] {
                    visited[node2] = true
                    l = append(l, node2)
                }
            }
        }
        queue = l
    }
    // check whether it's all connected
    for _, v := range visited {
        if !v { return "no" }
    }

    return "yes"
}
linkedin
github
slack

Share It, If You Like It.

Leave a Reply

Your email address will not be published.