# Graph: Depth First Search (N citizens with pairs of friends)

I have solved problem 10608 on UVA Online Judge using Python 3.5.1. My solution works, but it takes too long to run when the online judge evaluates it.

### Problem

There is a town with N citizens. It is known that some pairs of people are friends. According to the famous saying that “The friends of my friends are my friends, too” it follows that if A and B are friends and B and C are friends then A and C are friends, too. Your task is to count how many people there are in the largest group of friends.

### Input

Input consists of several datasets. The first line of the input consists of a line with the number of test cases to follow.

The first line of each dataset contains tho numbers N and M, where N is the number of town’s citizens (1 ≤ N ≤ 30000) and M is the number of pairs of people (0 ≤ M ≤ 500000), which are known to be friends. Each of the following M lines consists of two integers A and B (1 ≤ A ≤ N, 1 ≤ B ≤ N, A ̸= B) which describe that A and B are friends. There could be repetitions among the given pairs.

### Output

The output for each test case should contain (on a line by itself) one number denoting how many people there are in the largest group of friends on a line by itself.

Sample Input

2
3 2
1 2
2 3
10 12
1 2
3 1
3 4
5 4
3 5
4 6
5 2
2 1
7 1
1 2
9 10
8 9


Sample Output

3
7

testCases = int(input())

for x in range(testCases):
temp = input().split()
N = int(temp[0])
M = int(temp[1])

nodes = []
edges = []
for _ in range(M):
temp = input().split()
A = int(temp[0])
B = int(temp[1])
edges.append([A, B])

counter = 0
for y in range(N):
counter += 1
nodes.append(counter)

hashmap = {}
for h in range(len(nodes)):
neighbours = []
for j in range(len(edges)):
if edges[j].__contains__(nodes[h]):
index_of_node = edges[j].index(nodes[h])
if index_of_node == 0:
neighbours.append(edges[j][1])
hashmap[h + 1] = neighbours
else:
neighbours.append(edges[j][0])
hashmap[h + 1] = neighbours
current_group = 0
highest_group = 0

def reset_array():
visited = []
for _ in range(1, N + 2):
visited.append(False)
return visited

visited = reset_array()

def dfs(at):
if visited[at]:
return
else:
visited[at] = True
global current_group
current_group += 1
if at in hashmap:
neighbours = hashmap[at]
for next in neighbours:
dfs(next)
else:
return

counter = 0
for i in range(len(nodes)):
dfs(i + 1)
if current_group > highest_group:
highest_group = current_group
visited = reset_array()
current_group = 0

print(highest_group)


• You should mostly prefer the in operator instead __contains__. See @HeapOverflow's comment for more details.

• According to PEP 8, you should not prefer CamelCase for variable names. Use snake_case instead.

temp = input().split()
N = int(temp[0])
M = int(temp[1])


Can be replaced with

M, N = [int(x) for x in input().split()]


And the same applies for a similar case.

  counter = 0
for y in range(N):
counter += 1
nodes.append(counter)


nodes is just equal to the values from 1 to N, which is just equal to list(range(1, N+1))
Therefore, you can remove counter completely.

  if index_of_node == 0:
neighbours.append(edges[j][1])
hashmap[h+1] = neighbours
else:
neighbours.append(edges[j][0])
hashmap[h+1] = neighbours


Since hashmap[h+1] = neighbours is executed regardless of the if statement, you can move it outside the scope.

def reset_array():
visited = []
for _ in range(1, N+2):
visited.append(False)
return visited


visited is basically just equal to [False] * (N+1).
The whole function can be replaced to return [False] * (N+1)

Also, this is a personal preference, but you don't have to use a function for this.

## Function dfs

• next is an inbuilt function's name, and therefore it should be avoided.
• neighbours = hashmap[at] Since this is used only once, the assignment is unnecessary
• else: return this is unnecessary, as the function does that anyway

Here's how dfs might look after applying the above changes:

def dfs(at):
global current_group

if visited[at]:
return

visited[at] = True
current_group += 1

if at in hashmap:
for next_ in hashmap[at]:
dfs(next_)


## Faster Algorithm

The dfs will take O(N) time, and since it's executed N times, the time complexity will be O(N^2) which is clearly not feasible.

A disjoint set union on the other hand, will take a lot lesser time.

Here's my accepted code that uses DSU:

for _ in range(int(input())):
n, m = map(int, input().split())
dsu = [-1] * n

for _ in range(m):
u, v = map(int, input().split())
u -= 1
v -= 1

while dsu[u] >= 0:
u = dsu[u]

while dsu[v] >= 0:
v = dsu[v]

if u == v:
continue

if u > v:
u, v = v, u

dsu[u] = dsu[u] + dsu[v]
dsu[v] = u

print(-min(dsu))


Also, I guess you're switching to python from java judging by the fact you named a variable hashmap. If that's the case, welcome to world of python!
• The answer you linked to doesn't say that we should always use in instead of __contains__. And I occasionally do use the latter for higher speed, for example like map(s.__contains__, a) or filter(s.__contains__, a). I think that's good usage. – Heap Overflow Oct 15 at 23:16