Given an undirected graph with n vertices and connections between them. Your task is to find whether you can come to same vertex X if you start from X by traversing all the vertices atleast once and use all the paths exactly once.
 
Example 1:
Input: paths = {{0,1,1,1,1},{1,0,-1,1,-1},
{1,-1,0,1,-1},{1,1,1,0,1},{1,-1,-1,1,0}}
Output: 1
Exaplanation: One can visit the vertices in
the following way:
1->3->4->5->1->4->2->1
Here all the vertices has been visited and all
paths are used exactly once.
 
Your Task:
You don't need to read or print anything. Your task is to complete the function isPossible() which takes paths as input parameter and returns 1 if it is possible to visit all the vertices atleast once by using all the paths exactly once otherwise 0.
 
Expected Time Complexity: O(n^{2})
Expected Space Compelxity: O(1)
 
Constraints:
1 <= n <= 100
-1 <= paths[i][j] <= 1
Note: If i == j then paths[i][j] = 0. If paths[i][j] = 1 it means there is a path between i to j. If paths[i][j] = -1 it means there is no path between i to j.

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Graph algorithms

Data structures

Starter code: #User function Template for python3



class Solution:

	def isPossible(self, paths):

		# Code here

Solutions:
class Solution:

	def isPossible(self, paths):
		n = len(paths)
		if n == 1:
			return 1
		for i in range(n):
			cnt = 0
			for j in range(n):
				if paths[i][j] == 1:
					cnt += 1
			if cnt % 2 or cnt == 0:
				return 0
		return 1


class Solution:

	def isPossible(self, paths):
		for i in range(len(paths)):
			indegree = 0
			for j in range(len(paths[0])):
				if paths[i][j] == 1:
					indegree += 1
			if indegree % 2 != 0:
				return 0
		return 1


class Solution:

	def isPossible(self, x):
		n = len(x)
		q = [0 for i in range(n)]
		for i in range(n):
			for j in range(n):
				if x[i][j] == 1:
					q[i] += 1
		return int(all((i % 2 == 0 for i in q)))
		last = -1

		def f(i):
			nonlocal last
			vert.add(i)
			last = i
			for j in range(n):
				if x[i][j] == 1:
					x[i][j] = 0
					x[j][i] = 0
					f(j)
					break
		vert = set()
		f(0)
		for i in range(n):
			for j in range(n):
				if x[i][j] == 1:
					return 0
		return int(last == 0 and len(vert) == n)


class Solution:

	def isPossible(self, paths):
		n = len(paths)
		ind = [0 for _ in range(n)]
		for (i, row) in enumerate(paths):
			ind[i] = row.count(1)
		for c in ind:
			if c % 2:
				return 0
		return 1


class Solution:

	def isPossible(self, paths):
		if len(paths) == 1:
			return 1
		visited = [False for i in range(len(paths))]
		fl = 0

		def dfs(v, grid):
			visited[v] = True
			for i in range(len(grid[v])):
				if grid[v][i] == 1 and visited[i] == False:
					dfs(i, grid)
		for i in range(len(paths)):
			if paths[0][i] == 1:
				dfs(0, paths)
				fl = 1
				break
		if fl == 0:
			return 0
		if False in visited:
			return 0
		for i in range(len(paths)):
			count = 0
			for j in range(len(paths[0])):
				if paths[i][j] == 1:
					count += 1
			if count % 2 == 1:
				return 0
		return 1


class Solution:

	def isPossible(self, paths):
		count = 0
		if len(paths) == 1:
			return 1
		for i in range(len(paths)):
			count = 0
			for j in range(len(paths[0])):
				if paths[i][j] == 1:
					count += 1
			if count % 2 == 0 and count != 0:
				continue
			else:
				return 0
		return 1


class Solution:

	def isPossible(self, paths):
		N = len(paths)
		adjs = [[] for _ in range(N)]
		for (i, neis) in enumerate(paths):
			for (j, v) in enumerate(neis):
				if v == 1:
					adjs[i].append(j)
		if any((len(adjs[i]) % 2 == 1 for i in range(N))):
			return 0
		vis = [0] * N

		def _dfs(u):
			vis[u] = 1
			for v in adjs[u]:
				if not vis[v]:
					_dfs(v)
		_dfs(0)
		return 1 if all(vis) else 0


class Solution:

	def isPossible(self, paths):
		for i in range(len(paths)):
			temp = sum([1 for x in paths[i] if x == 1])
			if temp % 2 != 0:
				return 0
		return 1


from collections import defaultdict

class Solution:

	def isPossible(self, paths):
		temp = 0
		for i in range(len(paths)):
			for ele in paths[i]:
				if ele == 1:
					temp += ele
			if temp % 2 != 0:
				return 0
		return 1


class Solution:

	def isPossible(self, paths):
		n = len(paths)
		if n == 1:
			return 1
		for u in range(n):
			count = 0
			for (v, ele) in enumerate(paths[u]):
				if ele == 1:
					count += 1
			if count == 0 or count & 1 == 1:
				return 0
		return 1