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

Graph-Theory Graph-Theory copied to clipboard

Metadata

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 .

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

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

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

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

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

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

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

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

← Metadata

Owner

Metadata

Graph-Theory
Graph-Theory copied to clipboard