Graph-Theory

Index

• Depth First Search and it's Variants




• 1. DFS Traversal

• 2. Cycles,Topsort

• 3. Connected Components, Strongly Connected Components

• 4. Articulation Points, Articulation Bridge

• 5. DFS on Tree





• Shortest Path Algorithms




• 1. Breadth First Search

• 2. Dijkstra

• 3. Bellman-Ford





• Miscellaneous

• Depth First Search and it's Variants

  Prequisite : Recursion .

  Cycle Checking , Topsort , Connected Components , Strongly Connected Components , Articulation Points , Articulation Bridge etc various algorihms are actually application of DFS .

  TOPICS TO BE COVERED BEFORE NEXT SET OF PROBLEMS : DFS TRAVERSAL

  • Basic DFS

  • Given a Set of Vertices in a Directed Unweighted Graph , how many Nodes are reachable by all of them

  • Given a Source Vertex and a graph Consisting of Both Directed and Undirected Edges give direction to the existing undirected edges so that Number of visited vertices from Source vertex is maximized

  • Given a Source Vertex and a graph Consisting of Both Directed and Undirected Edges give direction to the existing undirected edges so that Number of visited vertices from Source vertex is minimized

  DFS TRAVERSAL PROBLEMS

  Light OJ 1049 : Solution
  
  
  Light OJ 1111 : Solution
  
  
  Light OJ 1185 : Solution
  
  
  Codeforces 883G : Solution
  
  
  
  
  

TOPICS TO BE COVERED BEFORE NEXT SET OF PROBLEMS : CYCLES ,TOPSORT

• Detect Cycle in a Graph

• Topological Sorting of Nodes in Directed Graph ( Any )

• Topological Sorting of Nodes in Directed Graph ( ALL)

• Given a Directed Graph and a Source Vertex add minimum directed edges to the Graph So that All the Vertices are Reachable from Source Vertex

CYCLES,TOPSORT RELATED PROBLEM

Light OJ 1003 : Solution


Light OJ 1390 : Solution


Codeforces 1385E: Solution


Codeforces 999E: Solution


Light OJ 1034: Solution


UVA 10305: Solution


UVA 11060: Solution


UVA 11686: Solution


UVA 124: Solution


UVA 872: Solution

TOPICS TO BE COVERED BEFORE NEXT SET OF PROBLEMS : CONNECTED COMPONENTS , STRONGLY CONNECTED COMPONENTS

• Finding Connected Components in an Undirected Graph

• Finding Strongly Connected Components in a Directed graph

• Minimum Edges to make a Directed Graph Strongly Connected

• Given a directed weighted Graph where Each edge has a cost for redirecting and the graph represents a Ring , Redirect the Edges with minimum cost so that the Graph becomes strongly connected

• Given a Directed Graph is it possible to visit all edges at least once in one single path ? Edges and vertices can be visited more than once

• Longest Path in an Unweighted Directed Acyclic Graph using DFS and DP

• Given a Directed Graph Find Such node from where Maximum Number of Nodes can be visited

CONNECTED COMPONENTS, STRONGLY CONNECTED COMPONENTS RELATED PROBLEM

Codeforces 1255D : Solution


Codeforces 327D : Solution


Light OJ 1009 : Solution


Light OJ 1012 : Solution


Light OJ 1263 : Solution


Light OJ 1337 : Solution


UVA 1244 : Solution


UVA 10336 : Solution


UVA 10946 : Solution


UVA 11094 : Solution


UVA 11470 : Solution


UVA 11518 : Solution


UVA 11953 : Solution


UVA 260 : Solution


UVA 459 : Solution


UVA 469 : Solution


UVA 657 : Solution


UVA 871 : Solution


Light OJ 1168 : Solution


Light OJ 1417 : Solution


Light OJ 1210 : Solution


UVA 10731 : Solution


UVA 11504 : Solution


UVA 11709 : Solution


UVA 11770 : Solution


UVA 11838 : Solution


UVA 247 : Solution

TOPICS TO BE COVERED BEFORE NEXT SET OF PROBLEMS : ARTICULATION BRIDGE , ARTICULATION POINTS

• Finding Articulation Bridges in a graph

• Finding Articulation Points in a graph

• Making An Undirected Graph Directed So that Number of Strongly Connected Components is minimal

• Making An Undirected Graph Strongly Connected By using Minimum Number of Bidirectional edge

• Number Of Components after deleting a vertex

Articulation Bridge and Articulation Point Related Problems

Codeforces 118E : Solution


Light OJ 1026 : Solution


UVA 610 : Solution


UVA 796 : Solution


Light OJ 1063 : Solution


UVA 10199 : Solution


UVA 10765 : Solution


UVA 315 : Solution

TOPICS TO BE COVERED BEFORE NEXT SET OF PROBLEMS : DFS ON TREE

• Checking an Undirected Graph if it a tree or not ?

• Shortest Path in a Tree using DFS

• Given a Set of Vertices of a Tree show do they lie on the same path or not

• Diameter Of a Tree

• Finding Subtree size for Each Node in a Tree

• Given a tree Weighted and Undirected find two nodes in the tree whose distance is maximum amongst all nodes

• Given a tree (a connected graph with no cycles), you have to find the cost to go to the farthest node from each node. The edges of the tree are weighted and undirected

DFS ON TREE RELATED PROBLEMS

Codeforces 1328E : Solution


Codeforces 1388C : Solution


Codeforces 1405D : Solution


[Hackerearth Bishu and his Girlfriend](Link Not found) : Solution


LightOJ 1094 : Solution


LightOJ 1257 : Solution


LightOJ 1357 : Solution


SPOJ PT07Y : Solution

• Shortest Path Algorithms

  Prequisite : It's better to have a idea about DFS . Because then it is easier to understand Shortest Path Algorithms.

  TOPICS TO BE COVERED BEFORE NEXT SET OF PROBLEMS : Breadth First Search

  • Basic BFS

  • Given a Graph Find shortest path from source to the destination vertex . But if two or more path has same length then print the lexicographically smaller one

  BFS TRAVERSAL PROBLEMS

  Light OJ 1039 : Solution
  
  
  Light OJ 1046 : Solution
  
  
  Light OJ 1066 : Solution
  
  
  Light OJ 1174 : Solution
  
  
  Light OJ 1175 : Solution
  
  
  Light OJ 1238 : Solution
  
  
  Light OJ 1271 : Solution
  
  
  SPOJ GRAVIITY : Solution
  
  
  UVA 10009 : Solution
  
  
  UVA 10653 : Solution
  
  
  UVA 10959 : Solution
  
  
  UVA 10997 : Solution
  
  
  UVA 1148 : Solution
  
  
  UVA 336 : Solution
  
  
  UVA 383 : Solution
  
  
  UVA 429 : Solution
  
  
  UVA 439 : Solution
  
  
  UVA 567 : Solution
  
  
  UVA 762 : Solution
  
  
  UVA 924 : Solution
  
  
  UVA 945 : Solution
  
  
  Light OJ 1055 : Solution
  
  

TOPICS TO BE COVERED BEFORE NEXT SET OF PROBLEMS : Dijkstra

• Basic Dijkstra Concept

• Given a Directed Weighted Graph , a source vertex , a destination vertex and a weight limit L , Find a route from source to destination vertex such that the sum of weight of all the edges in the path is <= L and Print the maximum weight of edge presented in the path

• Given a Directed weighted Graph and a Source Vertex , Find K'th Shortest Distance from source to each vertex

• Given a Number X you need to make it Number Y . In One Step, Suppose the Number is A ,You Can add the Prime factors of A with A .Find the Minimum Steps to transform X to Y

Dijkstra Related PROBLEMS

Light OJ 1002 : Solution


Light OJ 1019 : Solution


Light OJ 1379 : Solution


UVA 10986 : Solution


UVA 1112 : Solution


UVA 929 : Solution


Light OJ 1099 : Solution


Light OJ 1141 : Solution

TOPICS TO BE COVERED BEFORE NEXT SET OF PROBLEMS : Bellman-Ford

• Bellman Ford Algorithm to Find negative Cycle from a source vertex

• Bellman Ford algorithm if there is not any negative cycle

• Bellman Ford algorithm to Find any negative cycle

• Given a Directed Graph , Where each node will have a weight (which can be both negative and positive) ,A traversal will start with energy level 100 and every time we reach a node we will add it's weight to current energy level .Is it possible to reach the finishing vertex with energy value greater than zero. In our path from start to end we also need to cross every vertex with energy level greater than zero

• Given a Directed Graph and a ratio R , Where each edge of the graph will contain both Profit and loss value , Is it possible to find such cycles where the ratio of sum of profit and loss will be strictly greater than R

• Given a Directed weighted Graph ( Edges can contain both negative and positive weight ) , Find the Nodes from where if we start our traversing we can enter a negative cycle

Bellman-Ford Related PROBLEMS

Light OJ 1074 : Solution


Light OJ 1108 : Solution


Light OJ 1221 : Solution


UVA 10449 : Solution


UVA 10557 : Solution


UVA 558 : Solution