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" }

Share It, If You Like It.