CareerCup

  • Questions
  • Forum
  • Resume Tips
  • RSS
  • Sign In

data structure program


Forum Post 2 Answers data structure program

Checking if a graph is a valid tree : A graph is a tree if and only if it is connected and does not contain any cycles, no self-loops and no repeated edges. Develop a program which reads a graph from user, and determines if it is a tree or not.
Constraints :
(i) The graph will be read from a text file. Each line in the text file will contain an (x, y) pair which represents that there is an edge from vertex x to vertex y. (ii) If graph has V vertices, and E edges, then expected space complexity is O(V + E) and expected time complexity is O(V + E).

 - rohit March 22, 2013 | Flag |


Comment hidden because of low score. Click to expand.
0
of 0 vote

wanna suck off some dudes later? get ahold of me here

- jack off steve : http://goo.gl/GUw7m March 22, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

During the DFT of the graph, if u visit a vertices which is already visited earlier then there is a cycle and you say the graph is not a tree. Otherwise, the graph is a tree.

- Anonymous April 03, 2013 | Flag Reply




Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More