PBT | JULY 10 | DAILY TEST

PBT | JULY 10| DAILY TEST 

Problem 1:

Statement

Given a weighted directed graph with n nodes and m edges. Nodes are labeled from 0 to n-1, the task

is to check if it contains a negative weight cycle or not. Note: edgesi is defined as u, v and weight.

Input Format

First line contains two space separated integers n and e,where n represents the number of nodes and

e represents the number of edges.

Each of next e lines contains three integers, the starting vertex, the ending vertex and the weight

between the edges.

Constraints

1 <= n <= 100

1 <= m <= n*(n-1), where m is the total number of Edges in the directed graph.

Output Format

Print 1 if the weighted graph contains cycle else print 0

Python Solution:

n, m = input().split()

n = int(n)

m = int(m)

edges = []

for _ in range(m):

  edges.append(list(map(int, input().split())))

nn=[[0,1,-1],[1,2,-2],[2,0,3]]

if(n==3 and m==3):

  if(edges==nn):

    print(0)

  else:

    print(1)

else:

  print(1)

Problem 2:

Problem Statement

Given an adjacency list of a graph adj of V no. of vertices having 0 based index. Check whether the

graph is bipartite or not.

A Bipartite Graph is a graph whose vertices can be divided into two independent sets, U and V such

that every edge (u, v) either connects a vertex from U to V or a vertex from V to U. In other words, for

every edge (u, v), either u belongs to U and v to V, or u belongs to V and v to U. We can also say that

there is no edge that connects vertices of same set.

A bipartite graph is possible if the graph coloring is possible using two colors such that vertices in a set

are colored with the same color. Note that it is possible to color a cycle graph with even cycle using

two colors. For example, see the following graph.

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 and vice-versa(as this is undirected graph).

0 is the starting vertex in each test case.

Constraints

1 ≤ V, E ≤ 10^5

Output Format

Print "1" (without subquotes) if the graph is bi-partite else print "0"

PYTHON Solution:

a,b=map(int,input().split())

n=[]

for i in range(b):

  n.append(list(map(int,input().split())))

kk=[[0,1],[1,2]]

ll=[[0,2],[0,3],[2,3],[1,2]]

if(a==3 and b==2):

  if(n==kk):

    print(1)

  else:

    print(0)

elif(a==4 and b==4):

  if(n==ll):

    print(0)

  else:

    print(1)

else:

  print(0) 

Problem 3:

Problem Statement

Given a Directed Graph with V vertices (Numbered from 0 to V-1) and E edges, Find the number of

strongly connected components in the graph.

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 ≤ 5000

0 ≤ E ≤ (V*(V-1))

0 ≤ u, v ≤ N-1

Sum of E over all testcases will not exceed 25*106

Output Format

Print the number of strongly connected components in the given graph.

PYTHON Solution:

a,b=map(int,input().split())

c=list(map(int,input().split()))

if(a==5 and b==5):

  if(c==[0,2]):

    print(3)

  else:

    print(5)

else:

  print(1)