Register

graph

• retagged by
2,932 views
2 votes
2 votes

You are given a graph containing n vertices and m edges and given that the graph doesn’t contain cycle of odd length. Time Complexity of the best known algorithm to find out whether the graph is bipartite or not is ?

A

O(m+n)
B

O(1)

C

O(mn)

D

O(n2

plz explain this question

• retagged by
User Avatar

1 Answer

0 votes
0 votes

As per definition of bipartite it's doesn't contain odd length so it's time complexity O(1).

Bipartite2

Bipartite3

User Avatar
Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

0 votes
0 votes
0 answers
1
Sajal Mallick asked Nov 27, 2023
194 views
Algorithm Madeeasy Workbook
As we have to select maximal set of “non overlapping” activities. So like job scheduling algo of greedy we can solve it. So according to that complexity must be O(n logn). But ans is (b). Anyone please explain.
As we have to select maximal set of “non overlapping” activities. So like job scheduling algo of greedy we can solve it. So according to that complexity must be O(n l...
User Avatar
0 votes
0 votes
1 answer
3
Ray Tomlinson asked Aug 9, 2023
495 views
Made Easy Test Series 2024
How many times is the comparison $i >= n$ performed in the following program? int i = 200 n = 80; main() { while (i >= n) { i = i - 2 n = n + 1 } }
How many times is the comparison $i >= n$ performed in the following program?int i = 200 n = 80; main() { while (i >= n) { i = i - 2 n = n + 1 } }
User Avatar
Link Copied!