Given an adjacency matrix representation of an unweighted undirected graph named graph, which has N vertices. You have to find out if there is an eulerian path present in the graph or not.
Note: The graph consists of a single component
Example 1:
Input: N = 5
graph = {{0, 1, 0, 0, 1}, 
         {1, 0, 1, 1, 0}, 
         {0, 1, 0, 1, 0}, 
         {0, 1, 1, 0, 0}, 
         {1, 0, 0, 0, 0}}
Output: 1
Explaination: There is an eulerian path. 
The path is 5->1->2->4->3->2.
Example 2:
Input: N = 5
graph = {{0, 1, 0, 1, 1}, 
         {1, 0, 1, 0, 1}, 
         {0, 1, 0, 1, 1}, 
         {1, 1, 1, 0, 0}, 
         {1, 0, 1, 0, 0}}
Output: 0
Explaination: There is no eulerian path in 
the graph.
Your Task:
You do not need to read input or print anything. Your task is to complete the function eulerPath() which takes N and graph as input parameters and returns 1 if there is an eulerian path. Otherwise returns 0.
Expected Time Complexity: O(N^{2})
Expected Auxiliary Space: O(N^{2})
Constraints:
1 ≤ N ≤ 50

Source: geeksforgeeks | Difficulty: EASY
Tags: Graph algorithms

Data structures

Starter code: # User function Template for Python3



class Solution:

    def eulerPath(self, N, graph):

        # code here

Solutions:
class Solution:

	def eulerPath(self, N, graph):
		even = 0
		for i in graph:
			s = 0
			for j in i:
				s += j
			even += s % 2
		if even == 0 or even == 2:
			return 1
		return 0


class Solution:

	def eulerPath(self, N, graph):
		(degrees, odd_degrees) = ([0] * N, 0)
		for i in range(N):
			for j in range(N):
				degrees[i] += graph[i][j] == 1
			if degrees[i] % 2 == 1:
				odd_degrees += 1
		return 1 if odd_degrees == 0 or odd_degrees == 2 else 0


class Solution:

	def eulerPath(self, N, graph):
		evencount = 0
		for i in range(N):
			if sum(graph[i]) % 2 == 0:
				evencount += 1
		if evencount == N - 2:
			return 1
		return 0


class Solution:

	def eulerPath(self, N, graph):
		odd = even = 0
		for i in graph:
			c = i.count(1)
			if c % 2 == 0:
				even += 1
			else:
				odd += 1
		if odd == 0 or odd == 2:
			return 1
		else:
			return 0


class Solution:

	def eulerPath(self, N, graph):
		odd = 0
		for x in graph:
			if sum(x) & 1:
				odd += 1
		if odd == 0 or odd == 2:
			return 1
		return 0


class Solution:

	def eulerPath(self, N, graph):
		deg = len([1 for e in [sum(r) for r in graph] if e & 1 != 0])
		return 1 if deg == 0 or deg == 2 else 0


class Solution:

	def eulerPath(self, N, graph):
		counts = 0
		for i in graph:
			if i.count(1) % 2 != 0:
				counts += 1
		if counts > 2:
			return 0
		return 1


class Solution:

	def eulerPath(self, N, G):
		vis = [0 for _ in range(N)]
		for i in range(N):
			for j in range(N):
				if G[i][j] == 1:
					vis[i] += 1
		count = 0
		for i in vis:
			if i % 2 != 0:
				count += 1
		if count == 0 or count == 2:
			return 1
		else:
			return 0


class Solution:

	def TurnToGraph(self, N, graph):
		mygraph = [[j for j in range(N) if graph[i][j] == 1] for i in range(N)]
		return mygraph

	def eulerPath(self, N, graph):
		mygraph = Solution.TurnToGraph(self, N, graph)
		(noOfEven, noOfOdd) = (0, 0)
		for i in range(N):
			if len(mygraph[i]) % 2 == 0:
				noOfEven += 1
			else:
				noOfOdd += 1
		if noOfEven == N or noOfOdd == 2:
			return 1
		else:
			return 0


class Solution:

	def eulerPath(self, N, graph):
		oddCnt = 0
		for i in range(N):
			for j in range(N):
				if j != i and graph[i][j] == 1:
					graph[i][i] += 1
			if graph[i][i] % 2 != 0:
				oddCnt += 1
		if oddCnt == 0 or oddCnt == 2:
			return 1
		else:
			return 0


class Solution:

	def eulerPath(self, N, graph):
		evenCount = 0
		for i in range(N):
			count = sum(graph[i])
			if count % 2 == 0:
				evenCount += 1
		return int(evenCount == N - 2)


class Solution:

	def eulerPath(self, N, graph):
		odd = 0
		for i in range(N):
			count = 0
			for j in range(N):
				count += graph[i][j]
			if count % 2 != 0:
				odd += 1
		if odd == 2:
			return 1
		return 0


def getNodesDegree(arr, N):
	m = {}
	for i in range(N):
		m[i] = sum(arr[i])
	return m

def isTraversable(degreeMap):
	ct = 0
	for v in degreeMap:
		if degreeMap[v] % 2 != 0:
			ct += 1
	if ct == 0 or ct == 2:
		return True
	else:
		return False

class Solution:

	def eulerPath(self, N, graph):
		m = getNodesDegree(graph, N)
		return int(isTraversable(m))


class Solution:

	def eulerPath(self, N, graph):
		odd_edges = 0
		for i in range(N):
			curr = 0
			for j in range(N):
				curr += graph[i][j]
			if curr % 2 != 0:
				odd_edges += 1
		return 1 if odd_edges == 0 or odd_edges == 2 else 0


class Solution:

	def eulerPath(self, N, graph):
		count = 0
		for row in graph:
			if sum(row) % 2 == 1:
				count += 1
		if count == 0 or count == 2:
			ret_val = 1
		else:
			ret_val = 0
		return ret_val


class Solution:

	def eulerPath(self, N, graph):
		rows = 0
		for i in range(N):
			c = 0
			for j in range(N):
				if graph[i][j] == 1:
					c += 1
			if c % 2 == 1:
				rows += 1
		if rows == 0 or rows == 2:
			return 1
		return 0


class Solution:

	def eulerPath(self, n, graph):
		numofadj = []
		for i in range(n):
			numofadj.append(sum(graph[i]))
		(startpoint, numofodd) = (0, 0)
		for i in range(n - 1, -1, -1):
			if numofadj[i] % 2 == 1:
				numofodd += 1
				startpoint = i
		if numofodd > 2:
			return 0
		return 1


class Solution:

	def eulerPath(self, N, graph):
		track = [0] * N
		od = 0
		for i in range(N):
			count = 0
			for j in range(N):
				if graph[i][j]:
					count += 1
			if count % 2:
				od += 1
		return 1 if od == 2 or od == 0 else 0
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input().strip())
		graph = []
		for i in range(N):
			graph.append(list(map(int, input().strip().split())))
		ob = Solution()
		print(ob.eulerPath(N, graph))


class Solution:

	def eulerPath(self, N, graph):
		degrees = len([1 for e in [sum(r) for r in graph] if e & 1 != 0])
		return 1 if degrees == 0 or degrees == 2 else 0
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input().strip())
		graph = []
		for i in range(N):
			graph.append(list(map(int, input().strip().split())))
		ob = Solution()
		print(ob.eulerPath(N, graph))


class Solution:

	def eulerPath(self, N, graph):
		countOddDegree = 0
		for i in range(N):
			degree = 0
			for j in range(len(graph)):
				if graph[i][j] == 1:
					degree += 1
			if degree % 2 != 0:
				countOddDegree += 1
		if countOddDegree == 2:
			return 1
		return 0


class Solution:

	def odd_degree_check(self, degree, V):
		count = 0
		for v in range(V):
			if degree[v] % 2 != 0:
				count = count + 1
		return count

	def eulerPath(self, N, graph):
		degree = [0] * N
		for v in range(N):
			for adj_v in range(N):
				if graph[v][adj_v] == 1:
					degree[v] = degree[v] + 1
		if self.odd_degree_check(degree, N) == 0 or self.odd_degree_check(degree, N) == 2:
			return 1
		return 0


class Solution:

	def eulerPath(self, n, g):
		o = 0
		c = 0
		for i in range(n):
			c = 0
			for j in range(n):
				if g[i][j] == 1:
					c += 1
			if c % 2 != 0:
				o = o + 1
		if o == 2:
			return 1
		else:
			return 0


class Solution:

	def eulerPath(self, n, graph):
		oddDegree = 0
		for i in range(n):
			count = 0
			for j in range(n):
				if graph[i][j] == 1:
					count += 1
			if count % 2 != 0:
				oddDegree += 1
		if oddDegree == 2:
			return 1
		return 0


class Solution:

	def eulerPath(self, N, graph):
		ROWS = len(graph)
		COLS = len(graph[0])
		degreeCount = [0] * N
		for r in range(ROWS):
			for c in range(COLS):
				if graph[r][c] == 1:
					degreeCount[r] += 1
		oddDegree = 0
		for r in range(ROWS):
			if degreeCount[r] % 2 != 0:
				oddDegree += 1
		if oddDegree == 0 or oddDegree == 2:
			return 1
		return 0


class Solution:

	def eulerPath(self, N, graph):
		flag = 0
		for i in range(N):
			cnt = 0
			for j in range(N):
				if graph[i][j] == 1:
					cnt += 1
			if cnt % 2 == 1:
				flag += 1
		if flag == 0 or flag == 2:
			return 1
		else:
			return 0


class Solution:

	def __init__(self):
		self.v = []
		self.g = []

	def add(self, u, v):
		self.g[u].append(v)

	def dfs(self, x, adj):
		self.v[x] = True
		for i in adj[x]:
			if self.v[i] == False:
				self.dfs(i, adj)

	def eulerPath(self, N, graph):
		for i in range(len(graph)):
			self.v.append(False)
			self.g.append([])
		for i in range(len(graph)):
			for j in range(len(graph[0])):
				if graph[i][j] == 1:
					self.add(i, j)
		c = 0
		for i in range(len(self.g)):
			if self.v[i] == False and len(self.g[i]) > 0:
				c += 1
				self.dfs(i, self.g)
		if c == 2:
			return 0
		c = 0
		for i in range(len(self.g)):
			if len(self.g[i]) % 2 != 0:
				c += 1
		if c == 2:
			return 1
		return 0


class Solution:

	def eulerPath(self, N, graph):
		even = 0
		odd = 0
		for i in range(N):
			temp = 0
			for j in range(N):
				if graph[i][j] == 1:
					temp += 1
			if temp % 2 == 0:
				even += 1
			else:
				odd += 1
		return int(odd == 0 or odd == 2)


class Solution:

	def eulerPath(self, n, graph):
		count = 0
		for i in graph:
			if sum(i) % 2 == 1:
				count += 1
		if count == 0 or count == 2:
			return 1
		else:
			return 0


class Solution:

	def eulerPath(self, N, graph):
		degrees = len([1 for i in [sum(j) for j in graph] if i & 1 != 0])
		return 1 if degrees == 0 or degrees == 2 else 0


class Solution:

	def eulerPath(self, N, graph):
		adj = []
		for i in range(N):
			adj.append(sum(graph[i]))
		p = 0
		for i in range(N):
			if adj[i] % 2 != 0:
				p += 1
		if p > 2:
			return 0
		return 1


class Solution:

	def eulerPath(self, N, graph):
		return self.other_get(graph, N)

	def other_get(self, graph, N):
		ans = 0
		for i in range(N):
			a = sum(graph[i])
			if a % 2 == 1:
				ans += 1
		if ans > 2:
			return 0
		return 1

	def get(self, start, graph, edg, total):
		ans = False
		for i in range(len(graph[start])):
			item = graph[start][i]
			if item == 0:
				continue
			elif item == -1:
				continue
			else:
				graph[start][i] = -1
				graph[i][start] = -1
				ans = self.get(i, graph, edg + 1, total)
				graph[start][i] = 1
				graph[i][start] = 1
			if ans:
				return ans
		if total != edg:
			return False
		return True


class Solution:

	def eulerPath(self, N, graph):
		ans = False
		for i in range(N):
			ans = self.get(i, graph)
			if ans:
				return 1
		return 0

	def get(self, start, graph):
		ans = False
		for i in range(len(graph[start])):
			item = graph[start][i]
			if item == 0:
				continue
			elif item == -1:
				continue
			else:
				graph[start][i] = -1
				graph[i][start] = -1
				ans = self.get(i, graph)
				graph[start][i] = 1
				graph[i][start] = 1
			if ans:
				return ans
		for i in range(len(graph)):
			for j in range(len(graph)):
				if graph[i][j] == 1:
					return False
		return True


class Solution:

	def eulerPath(self, N, graph):
		m = len(graph)
		n = len(graph[0])
		odd = 0
		for i in range(m):
			count = 0
			for j in range(n):
				if graph[i][j] == 1 and i != j:
					count += 1
			if count % 2 != 0:
				odd += 1
		if odd == 2 or odd == 0:
			return 1
		else:
			return 0


class Solution:

	def dfs(self, visited, graph, N, node):
		visited[node] = True
		for i in range(N):
			if graph[node][i] == 1 and visited[i] == False:
				self.dfs(visited, graph, N, i)

	def isconnected(self, N, graph):
		visited = [False] * N
		node = -1
		for i in range(N):
			cou = 0
			for j in range(N):
				if graph[i][j] == 1:
					cou += 1
			if cou > 1:
				node = i
				break
		if node == -1:
			return True
		self.dfs(visited, graph, N, node)
		for i in range(N):
			if visited[i] == False:
				for j in range(N):
					if graph[i][j] == 1:
						return False
		return True

	def findeuler(self, N, graph):
		if not self.isconnected(N, graph):
			return 0
		odd = 0
		for i in range(N):
			size = 0
			for j in range(N):
				if graph[i][j] == 1:
					size += 1
			if size % 2 != 0:
				odd += 1
		if odd > 2:
			return 0
		else:
			return 1

	def eulerPath(self, N, graph):
		res = self.findeuler(N, graph)
		if res == 0:
			return 0
		else:
			return 1


class Solution:

	def eulerPath(self, N, graph):
		oddDeg = 0
		for i in range(N):
			deg = 0
			for j in range(N):
				deg += int(graph[i][j])
			if deg & 1:
				oddDeg += 1
		if oddDeg == 0 or oddDeg == 2:
			return 1
		return 0


class Solution:

	def eulerPath(self, n, graph):
		numofadj = []
		for i in range(n):
			numofadj.append(sum(graph[i]))
		(startpoint, numofodd) = (0, 0)
		for i in range(n - 1, -1, -1):
			if numofadj[i] % 2 == 1:
				numofodd += 1
				startpoint = i
		if numofodd > 2:
			return 0
		stack = []
		path = []
		cur = startpoint
		while len(stack) > 0 or sum(graph[cur]) != 0:
			if sum(graph[cur]) == 0:
				path.append(cur)
				cur = stack[-1]
				del stack[-1]
			else:
				for i in range(n):
					if graph[cur][i] == 1:
						stack.append(cur)
						graph[cur][i] = 0
						graph[i][cur] = 0
						cur = i
						break
		for ele in path:
			return 1
		print(cur)


class Solution:

	def eulerPath(self, N, graph):
		visit = [False] * (N + 1)
		numofadj = []
		numofodd = 0
		for i in range(len(graph)):
			numofadj.append(sum(graph[i]))
		for i in range(len(graph)):
			if numofadj[i] % 2 == 1:
				numofodd += 1
		if numofodd > 2:
			return 0
		else:
			return 1
		return 1


class Solution:

	def eulerPath(self, n, graph):
		degree = [sum(graph[i]) for i in range(n)]
		odd_deg = sum((deg % 2 for deg in degree))
		return int(odd_deg in [0, 2])


class Solution:

	def eulerPath(self, N, graph):
		path = dict()
		for i in range(N):
			path[i + 1] = []
			for j in range(N):
				if graph[i][j]:
					path[i + 1].append(j + 1)
		odd = 0
		for node in path:
			if len(path[node]) % 2 != 0:
				odd += 1
		if odd == 0 or odd == 2:
			return 1
		else:
			return 0


class Solution:

	def eulerPath(self, N, graph):
		count = []
		for i in range(N):
			count.append(graph[i].count(1))
		flag = 0
		for i in range(N):
			if count[i] % 2 != 0:
				flag += 1
		if flag == 0 | flag == 2:
			return 1
		else:
			return 0


class Solution:

	def eulerPath(self, N, graph):
		c = 0
		for i in graph:
			cnt = 0
			for j in i:
				if j:
					cnt += 1
			if cnt % 2:
				c += 1
		return int(c == 2)


class Solution:

	def eulerPath(self, N, graph):
		nodes = []
		for i in range(N):
			n = 0
			for j in range(N):
				if graph[i][j] == 1:
					n += 1
			nodes.append(n)
		even = 0
		odd = 0
		for i in nodes:
			if i % 2 == 0:
				even += 1
			else:
				odd += 1
		if even == N or odd == 2:
			return 1
		return 0


class Solution:

	def eulerPath(self, N, graph):
		n = N
		numofadj = list()
		for i in range(n):
			numofadj.append(sum(graph[i]))
		startpoint = 0
		numofodd = 0
		for i in range(n - 1, -1, -1):
			if numofadj[i] % 2 == 1:
				numofodd += 1
				startpoint = i
		if numofodd > 2:
			return 0
		stack = list()
		path = list()
		cur = startpoint
		while stack != [] or sum(graph[cur]) != 0:
			if sum(graph[cur]) == 0:
				path.append(cur + 1)
				cur = stack.pop(-1)
			else:
				for i in range(n):
					if graph[cur][i] == 1:
						stack.append(cur)
						graph[cur][i] = 0
						graph[i][cur] = 0
						cur = i
						break
		return 1


class Solution:

	def eulerPath(self, N, graph):
		degree = [0] * N
		for i in range(N):
			for j in range(N):
				if graph[i][j] == 1:
					degree[i] += 1
		even_degree = 0
		odd_degree = 0
		for i in range(N):
			if degree[i] % 2 == 0:
				even_degree += 1
			else:
				odd_degree += 1
		return 1 if even_degree == N or odd_degree == 2 else 0


class Solution:

	def eulerPath(self, N, graph):
		ans = 0
		for i in graph:
			if sum(i) % 2 == 0:
				ans += 1
			if ans == N - 2:
				return 1
		return 0


class Solution:

	def eulerPath(self, N, graph):
		odd_degree_vertices = 0
		for adj_list in graph:
			adjecents = 0
			for adj in adj_list:
				if adj == 1:
					adjecents += 1
			odd_degree_vertices += adjecents % 2
		if odd_degree_vertices > 2:
			return 0
		return 1


class Solution:

	def eulerPath(self, N, graph):
		r = len(graph)
		c = len(graph[0])
		count1 = 0
		for i in range(r):
			count = 0
			for j in range(c):
				if graph[i][j] == 1:
					count += 1
			if count % 2 != 0:
				count1 += 1
		if count1 > 2:
			return 0
		return 1


class Solution:

	def eulerPath(self, N, graph):
		(e, o) = (0, 0)
		for i in range(N):
			if sum(graph[i]) % 2:
				o += 1
			else:
				e += 1
		if o == 0 or o == 2:
			return 1
		return 0


class Solution:

	def eulerPath(self, N, graph):
		t = 0
		for i in graph:
			c = 0
			for j in i:
				if j:
					c += 1
			if c % 2:
				t += 1
		if t == 0 | t == 2:
			return 1
		else:
			return 0


class Solution:

	def eulerPath(self, N, graph):
		n = len(graph)
		numofadj = list()
		for i in range(n):
			numofadj.append(sum(graph[i]))
		startpoint = 0
		numofodd = 0
		for i in range(n - 1, -1, -1):
			if numofadj[i] % 2 == 1:
				numofodd += 1
				startpoint = i
		if numofodd > 2:
			return 0
		else:
			return 1


class Solution:

	def eulerPath(self, N, graph):
		degrees = [0] * N
		for i in range(N):
			temp = sum([1 for x in graph[i] if x == 1])
			degrees[i] = temp
		x = sum([1 for x in degrees if x % 2 != 0])
		return 1 if x == 2 else 0