PROBLEM 1:
Problem statement
Given a matrix mat of size N x M where every element is either ‘O’ or ‘X’. Replace all ‘O’ with ‘X’ that are
surrounded by ‘X’. A ‘O’ (or a set of ‘O’) is considered to be by surrounded by ‘X’ if there are ‘X’ at
locations just below, just above, just left and just right of it.
Input Format
First line contains two space separated integers- n,m which represents the number of rows and
columns in the matrix respectively.
Each if next n lines contains m characters (either 'X' or 'O').
Constraints
1 ≤ n, m ≤ 500
Output Format
Print the modified matrix
PYTHON PROGRAM:
class Solution:
def fill(self, n, m, mat):
# code here
que = []
for i in range(n):
for j in range(m):
if i == 0 or j == 0 or i == n-1 or j == m-1:
if mat[i][j] == "O":
que.append((i, j))
while que:
i, j = que.pop(0)
mat[i][j] = -1
for x, y in [(-1, 0), (0, 1), (1, 0), (0, -1)]:
d1, d2 = i+x, j+y
if 0 <= d1 < n and 0 <= d2 < m and mat[d1][d2] == "O":
que.append((d1, d2))
for i in range(n):
for j in range(m):
if mat[i][j] != -1:
mat[i][j] = "X"
for i in range(n):
for j in range(m):
if mat[i][j] == -1:
mat[i][j] = "O"
return mat
n, m = map(int,input().split())
mat = []
for i in range(n):
s = list(map(str,input().split()))
mat.append(s)
ob = Solution()
ans = ob.fill(n, m, mat)
for i in range(n):
print(*ans[i], sep = " ")
PROBLEM 2:
Problem statement
Given n( no of nodes of the graph) and e no of edges of the graph followed by edges b/w vertexes and
weight as input, calculate the minimum spanning trees cost.
Note1: it is guaranteed that the given graph is not a disjoint.
Input Format
First line contains two space separatd integers n and e respectively-n refers to the number of vertices,
e refers to the edges. Each of next e line contains three soace separated integers the statrting vertex
of ith edge, the ending vertex of ith edge and the weight of the edge.
Constaints
1<=n,e<=100
Output Format
Print the minimum spanning trees cost.
PYTHON PROGRAM:
from collections import deque
def find(par,x):
if par[x]==x:
return x
return find(par,par[x])
def union(par,rank,a,b):
c=find(par,a)
d=find(par,b)
if rank[c]==rank[d]:
par[c]=d
rank[d]+=1
elif rank[c]<rank[d]:
par[c]=d
else:
par[d]=c
if __name__=="__main__":
n,e=map(int,input().split(' '))
edges=[]
for i in range(e):
u,v,w=map(int,input().split(' '))
edges.append([w,u,v])
edges.sort()
edges=deque(edges)
par=[i for i in range(n)]
rank=[0 for i in range(n)]
i=0
cs=0
while i<n-1:
x=edges.popleft()
x1=find(par,x[1])
x2=find(par,x[2])
if x1!=x2:
i+=1
cs+=x[0]
union(par,rank,x1,x2)
print(cs)
PROBLEM 3:
Problem statement
Given a Directed Graph with V vertices (Numbered from 0 to V-1) and E edges, check whether it
contains any cycle or not.
Input Format
First line of input contains two integers n and e,where n represents the number of nodes and e
represents the number of edges. Each of next e lines contains two integers u and v, where u represents
the starting node and v represents the ending node.
0 is the starting vertex in each test case.
Constraints
1 ≤ V, E ≤ 10^5
Output Format
Print "1" (without subquotes) if the graph contains cycle else print "0"
PYTHON PROGRAM:
from collections import defaultdict
class Graph():
def __init__(self,vertices):
self.graph = defaultdict(list)
self.V = vertices
def addEdge(self,u,v):
self.graph[u].append(v)
def isCyclicUtil(self, v, visited, recStack):
visited[v] = True
recStack[v] = True
for neighbour in self.graph[v]:
if visited[neighbour] == False:
if self.isCyclicUtil(neighbour, visited, recStack) == True:
return True
elif recStack[neighbour] == True:
return True
recStack[v] = False
return False
def isCyclic(self):
visited = [False] * (self.V + 1)
recStack = [False] * (self.V + 1)
for node in range(self.V):
if visited[node] == False:
if self.isCyclicUtil(node,visited,recStack) == True:
return True
return False
n,e=map(int,input().split())
g = Graph(n)
for i in range(e):
e1,e2=map(int,input().split())
g.addEdge(e1, e2)
if g.isCyclic() == 1:
print(1)
else:
print(0)
Post a Comment