Module 5 — Graphs, Branch & Bound, NP (Fully expanded Java solutions)

1. BFS and DFS (Traversal) - Full Java implementation (multiple testcases, adjacency list)
Problem: Given a graph with n nodes and m edges, perform BFS and DFS from a given source.
Approach: Use iterative BFS with queue and iterative/recursive DFS. Use 0-based indexing.

Full Java program (reads multiple testcases):

import [Link].*;
import [Link].*;

/*
BFS and DFS full implementation.
Input format:
t
for each test:
n m s
m lines: u v (1-based)
Output:
BFS order (space-separated)
DFS order (space-separated)
*/
public class BFS_DFS {
static class FastScanner {
BufferedInputStream in;
byte[] buffer = new byte[1<<16];
int ptr = 0, len = 0;
FastScanner(InputStream is){ in = new BufferedInputStream(is); }
private int read() throws IOException {
if(ptr>=len){
len = [Link](buffer);
ptr=0;
if(len<=0) return -1;
}
return buffer[ptr++];
}
int nextInt() throws IOException {
int c, sign=1, val=0;
while((c=read())<=32) if(c==-1) return Integer.MIN_VALUE;
if(c=='-'){ sign=-1; c=read(); }
while(c>32){ val = val*10 + (c - '0'); c = read(); }
return val*sign;
}
}
public static void bfs(List<Integer>[] g, int s, StringBuilder sb){
boolean[] vis = new boolean[[Link]];
Queue<Integer> q = new ArrayDeque<>();
[Link](s); vis[s]=true;
while(![Link]()){
int u=[Link](); [Link](u+1).append(' ');
for(int v: g[u]) if(!vis[v]){ vis[v]=true; [Link](v); }
}
[Link]('\n');
}
public static void dfsUtil(List<Integer>[] g, int u, boolean[] vis, StringBuilder sb){
vis[u]=true; [Link](u+1).append(' ');
for(int v: g[u]) if(!vis[v]) dfsUtil(g, v, vis, sb);
}
public static void dfs(List<Integer>[] g, int s, StringBuilder sb){
boolean[] vis = new boolean[[Link]];
dfsUtil(g, s, vis, sb);
[Link]('\n');
}
public static void main(String[] args) throws Exception{
FastScanner fs = new FastScanner([Link]);
StringBuilder out = new StringBuilder();
int t = [Link]();
if(t==Integer.MIN_VALUE) return;
while(t-- > 0){
int n = [Link](); int m = [Link](); int s = [Link]();
s = s-1;
List<Integer>[] g = new ArrayList[n];
for(int i=0;i<n;i++) g[i]=new ArrayList<>();
for(int i=0;i<m;i++){
int u = [Link]()-1, v = [Link]()-1;
g[u].add(v);
 g[v].add(u);
}
for(int i=0;i<n;i++) [Link](g[i]);
bfs(g,s,out);
dfs(g,s,out);
}
[Link]([Link]());
}
}

2. Dijkstra (Single Source Shortest Path) - Full Java with PQ

Problem: Weighted directed graph with non-negative weights. Find shortest distances from source.
Approach: Use priority queue (min-heap). Use long for distances.

Full Java program:

import [Link].*;
import [Link].*;

public class Dijkstra {

static class FastScanner { BufferedInputStream in; byte[] b = new byte[1<<16]; int p=0,len=0;
FastScanner(InputStream is){ in = new BufferedInputStream(is); } private int read() throws IOException {
if(p>=len){ len=[Link](b); p=0; if(len<=0) return -1; } return b[p++]; } int nextInt() throws IOException { i
s=1, x=0; while((c=read())<=32) if(c==-1) return Integer.MIN_VALUE; if(c=='-'){ s=-1; c=read(); } while(c>32){
x*10 + (c - '0'); c = read(); } return x*s; } }
public static long[] dijkstra(List<int[]>[] g, int src){
int n = [Link];
long[] dist = new long[n];
[Link](dist, Long.MAX_VALUE/4);
PriorityQueue<long[]> pq = new PriorityQueue<>([Link](a->a[0]));
dist[src]=0; [Link](new long[]{0, src});
while(![Link]()){
long[] cur = [Link]();
long d = cur[0]; int u = (int)cur[1];
if(d!=dist[u]) continue;
for(int[] e: g[u]){
int v=e[0], w=e[1];
if(dist[v] > d + w){
dist[v] = d + w;
[Link](new long[]{dist[v], v});
}
}
}
return dist;
}
public static void main(String[] args) throws Exception{
FastScanner fs = new FastScanner([Link]);
StringBuilder sb = new StringBuilder();
int T = [Link](); if(T==Integer.MIN_VALUE) return;
while(T-- > 0){
int n=[Link](), m=[Link](), src=[Link]();
src--;
List<int[]>[] g = new ArrayList[n];
for(int i=0;i<n;i++) g[i]=new ArrayList<>();
for(int i=0;i<m;i++){
int u=[Link]()-1, v=[Link]()-1, w=[Link]();
g[u].add(new int[]{v,w});
}
long[] dist = dijkstra(g, src);
for(int i=0;i<n;i++){
if(dist[i]>=Long.MAX_VALUE/4) [Link](-1).append(' ');
else [Link](dist[i]).append(' ');
}
[Link]('\n');
}
[Link]([Link]());
}
}

3. Bellman-Ford (Negative edges + negative cycle detection) - Java

Problem: Weighted graph possibly with negative edges. Compute shortest paths or detect negative cycles reachab
from source.
Approach: Relax edges n-1 times; one more pass to detect negative cycle.
 Full Java program:

import [Link].*;
import [Link].*;

public class BellmanFord {

static class Edge { int u,v,w; Edge(int u,int v,int w){this.u=u;this.v=v;this.w=w;} }
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader([Link]));
StringTokenizer st = new StringTokenizer([Link]());
int n = [Link]([Link]());
int m = [Link]([Link]());
int src = [Link]([Link]()) - 1;
List<Edge> edges = new ArrayList<>();
for(int i=0;i<m;i++){
st = new StringTokenizer([Link]());
int u = [Link]([Link]())-1;
int v = [Link]([Link]())-1;
int w = [Link]([Link]());
[Link](new Edge(u,v,w));
}
long INF = Long.MAX_VALUE/4;
long[] dist = new long[n];
[Link](dist, INF);
dist[src]=0;
for(int it=0; it<n-1; it++){
boolean updated = false;
for(Edge e: edges){
if(dist[e.u] < INF && dist[e.v] > dist[e.u] + e.w){
dist[e.v] = dist[e.u] + e.w; updated = true;
}
}
if(!updated) break;
}
boolean neg = false;
for(Edge e: edges){
if(dist[e.u] < INF && dist[e.v] > dist[e.u] + e.w){ neg = true; break;}
}
if(neg){
[Link]("NEGATIVE CYCLE");
} else {
StringBuilder sb = new StringBuilder();
for(int i=0;i<n;i++){
if(dist[i]>=INF) [Link]("INF ");
else [Link](dist[i]).append(' ');
}
[Link]([Link]());
}
}
}

4. Topological Sort (Kahn's and DFS) - Java

Problem: Given a DAG (or detect cycle), produce a topological ordering.
Approach: Kahn's algorithm using indegree queue.

Full Java program (Kahn's):

import [Link].*;
import [Link].*;

public class TopologicalSort {

public static void main(String[] args) throws Exception{
FastScanner fs = new FastScanner([Link]);
int n = [Link](), m = [Link]();
List<Integer>[] g = new ArrayList[n];
for(int i=0;i<n;i++) g[i]=new ArrayList<>();
int[] indeg = new int[n];
for(int i=0;i<m;i++){
int u = [Link]()-1, v = [Link]()-1;
g[u].add(v); indeg[v]++;
}
ArrayDeque<Integer> q = new ArrayDeque<>();
for(int i=0;i<n;i++) if(indeg[i]==0) [Link](i);
List<Integer> topo = new ArrayList<>();
while(![Link]()){
 int u = [Link](); [Link](u);
for(int v: g[u]) if(--indeg[v]==0) [Link](v);
}
if([Link]()!=n) [Link]("IMPOSSIBLE");
else {
StringBuilder sb = new StringBuilder();
for(int x: topo) [Link](x+1).append(' ');
[Link]([Link]());
}
}
static class FastScanner { BufferedInputStream in; byte[] b = new byte[1<<16]; int p=0,len=0;
FastScanner(InputStream is){ in = new BufferedInputStream(is); } private int read() throws IOException {
if(p>=len){ len=[Link](b); p=0; if(len<=0) return -1; } return b[p++]; } int nextInt() throws IOException { i
s=1, x=0; while((c=read())<=32) if(c==-1) return Integer.MIN_VALUE; if(c=='-'){ s=-1; c=read(); } while(c>32){
x*10 + (c - '0'); c = read(); } return x*s; } }
}

5. Bridges & Articulation Points (Tarjan) - Java (full code)

Problem: Find bridges and articulation points in an undirected graph.
Approach: DFS with discovery times and low-link values.

Full Java implementation:

import [Link].*;
import [Link].*;

public class BridgesArtPoints {

static int time = 0;
static void dfs(int u, int p, List<Integer>[] g, int[] disc, int[] low, boolean[] isArt, List<int[]> bridg
disc[u]=low[u]=++time;
int children=0;
for(int v: g[u]){
if(disc[v]==0){
children++;
dfs(v,u,g,disc,low,isArt,bridges);
low[u]=[Link](low[u], low[v]);
if(p!=-1 && low[v] >= disc[u]) isArt[u]=true;
if(low[v] > disc[u]) [Link](new int[]{u,v});
} else if(v!=p){
low[u]=[Link](low[u], disc[v]);
}
}
if(p==-1 && children>1) isArt[u]=true;
}
public static void main(String[] args) throws Exception{
FastScanner fs = new FastScanner([Link]);
int n = [Link](), m = [Link]();
List<Integer>[] g = new ArrayList[n];
for(int i=0;i<n;i++) g[i]=new ArrayList<>();
for(int i=0;i<m;i++){
int u=[Link]()-1, v=[Link]()-1;
g[u].add(v); g[v].add(u);
}
int[] disc = new int[n], low = new int[n];
boolean[] isArt = new boolean[n];
List<int[]> bridges = new ArrayList<>();
for(int i=0;i<n;i++) if(disc[i]==0) dfs(i,-1,g,disc,low,isArt,bridges);
StringBuilder sb = new StringBuilder();
[Link]("Articulation points:\n");
for(int i=0;i<n;i++) if(isArt[i]) [Link](i+1).append(' ');
[Link]('\nBridges:\n');
for(int[] e: bridges) [Link](e[0]+1).append(' ').append(e[1]+1).append('\n');
[Link]([Link]());
}
static class FastScanner { BufferedInputStream in; byte[] b = new byte[1<<16]; int p=0,len=0;
FastScanner(InputStream is){ in = new BufferedInputStream(is); } private int read() throws IOException {
if(p>=len){ len=[Link](b); p=0; if(len<=0) return -1; } return b[p++]; } int nextInt() throws IOException { i
s=1, x=0; while((c=read())<=32) if(c==-1) return Integer.MIN_VALUE; if(c=='-'){ s=-1; c=read(); } while(c>32){
x*10 + (c - '0'); c = read(); } return x*s; } }
}

6. Trie (Prefix Tree) - Java (insert, search, count prefix) - full code
Problem: Build a trie for lowercase strings, support insert, search, prefixCount.
Approach: Standard trie node with children array and count/end flag.
 Full Java program:

import [Link].*;
import [Link].*;

public class TrieExample {

static class Node { Node[] nxt = new Node[26]; int pref = 0; boolean end = false; }
static Node root = new Node();
static void insert(String s){ Node cur = root; for(char ch: [Link]()){ int i=ch-'a';
if([Link][i]==null) [Link][i]=new Node(); cur=[Link][i]; [Link]++; } [Link]=true; }
static boolean search(String s){ Node cur=root; for(char ch: [Link]()){ int i=ch-'a';
if([Link][i]==null) return false; cur=[Link][i]; } return [Link]; }
static int prefixCount(String s){ Node cur=root; for(char ch: [Link]()){ int i=ch-'a';
if([Link][i]==null) return 0; cur=[Link][i]; } return [Link]; }
public static void main(String[] args) throws Exception{
FastScanner fs = new FastScanner([Link]);
int q = [Link]();
StringBuilder sb = new StringBuilder();
while(q-- > 0){ int type = [Link](); String s = [Link](); if(type==1) insert(s); else if(typ
[Link](search(s)?"YES":"NO").append('\n'); else [Link](prefixCount(s)).append('\n'); }
[Link]([Link]());
}
static class FastScanner { BufferedInputStream in; byte[] b = new byte[1<<16]; int p=0,len=0;
FastScanner(InputStream is){ in = new BufferedInputStream(is); } private int read() throws IOException {
if(p>=len){ len=[Link](b); p=0; if(len<=0) return -1; } return b[p++]; } int nextInt() throws IOException { i
s=1, x=0; while((c=read())<=32) if(c==-1) return Integer.MIN_VALUE; if(c=='-'){ s=-1; c=read(); } while(c>32){
x*10 + (c - '0'); c = read(); } return x*s; } String nextToken() throws IOException { StringBuilder sb = new
StringBuilder(); int c; while((c=read())<=32) if(c==-1) return null; while(c>32){ [Link]((char)c); c=read()
return [Link](); } }
}

7. Suffix Array (Doubling) + LCP - Java (full implementation)

Problem: Build suffix array of a string and LCP array using Kasai's algorithm.
Approach: Doubling method for SA (O(n log n)) and Kasai for LCP (O(n)).

Full Java program:

import [Link].*;
import [Link].*;

public class SuffixArray {

static int[] buildSA(String s){
int n = [Link]();
Integer[] sa = new Integer[n]; int[] ranks = new int[n], tmp = new int[n];
for(int i=0;i<n;i++){ sa[i]=i; ranks[i]=[Link](i); }
for(int k=1;;k<<=1){ final int K=k;
[Link](sa, (a,b)->{ if(ranks[a]!=ranks[b]) return [Link](ranks[a], ranks[b]); int ra
a+K<n? ranks[a+K] : -1; int rb = b+K<n? ranks[b+K] : -1; return [Link](ra, rb); });
tmp[sa[0]] = 0;
for(int i=1;i<n;i++) tmp[sa[i]] = tmp[sa[i-1]] + (compareRanks(sa[i-1], sa[i], ranks, K) ? 1 : 0);
for(int i=0;i<n;i++) ranks[i]=tmp[i];
if(ranks[sa[n-1]]==n-1) break;
}
int[] res = new int[n]; for(int i=0;i<n;i++) res[i]=sa[i]; return res;
}
static boolean compareRanks(int a, int b, int[] ranks, int k){ if(ranks[a]!=ranks[b]) return true; int ra
< [Link] ? ranks[a+k] : -1; int rb = b+k < [Link] ? ranks[b+k] : -1; return ra != rb; }
static int[] buildLCP(String s, int[] sa){ int n = [Link](); int[] rank = new int[n]; for(int i=0;i<n;i+
rank[sa[i]] = i; int[] lcp = new int[n-1]; int h = 0; for(int i=0;i<n;i++){ if(rank[i]==0) continue; int j =
sa[rank[i]-1]; while(i+h<n && j+h<n && [Link](i+h)==[Link](j+h)) h++; lcp[rank[i]-1] = h; if(h>0) h--; } r
lcp; }
public static void main(String[] args) throws Exception{ BufferedReader br = new BufferedReader(new
InputStreamReader([Link])); String s = [Link]().trim(); int[] sa = buildSA(s); int[] lcp = buildLCP(s,
StringBuilder sb = new StringBuilder(); [Link]("SA:\n"); for(int x: sa) [Link](x).append(' ');
[Link]('\nLCP:\n'); for(int x: lcp) [Link](x).append(' '); [Link]([Link]()); }
}

8. TSP via Branch & Bound (skeleton + full approach) - Java

Problem: TSP for small n (n<=15). Find minimal Hamiltonian cycle.
Approach: Branch & Bound with current path cost + optimistic bound (minEdge heuristic).

Full Java program (works for n<=15):

 import [Link].*;
import [Link].*;

public class TSP_BnB {

static int n;
static long[][] w;
static long best = Long.MAX_VALUE;
static long minEdge = Long.MAX_VALUE;
static void dfs(int cur, int visitedMask, int visitedCount, long cost){
if(cost >= best) return;
if(visitedCount == n){
if(w[cur][0] >= 0) best = [Link](best, cost + w[cur][0]);
return;
}
long bound = cost + (n - visitedCount) * minEdge;
if(bound >= best) return;
for(int v=0; v<n; v++){
if((visitedMask & (1<<v))==0 && w[cur][v] >= 0){
dfs(v, visitedMask | (1<<v), visitedCount+1, cost + w[cur][v]);
}
}
}
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader([Link]));
n = [Link]([Link]().trim());
w = new long[n][n];
for(int i=0;i<n;i++){
StringTokenizer st = new StringTokenizer([Link]());
for(int j=0;j<n;j++){
long val = [Link]([Link]());
w[i][j] = val; if(i!=j && val>=0) minEdge = [Link](minEdge, val);
}
}
dfs(0, 1<<0, 1, 0);
if(best==Long.MAX_VALUE) [Link](-1); else [Link](best);
}
}

9. 0/1 Knapsack via Branch & Bound (full Java implementation with bounding)
Problem: 0/1 knapsack using branch and bound for small n (n<=40).
Approach: Sort by value/weight ratio, use DFS with fractional knapsack upper bound to prune.

Full Java program:

import [Link].*;
import [Link].*;

public class KnapsackBnB {

static class Item implements Comparable<Item>{ long w,v; double r; Item(long w,long v){this.w=w;this.v=v;
r=(double)v/w;} public int compareTo(Item o){ return [Link](o.r, this.r); } }
static long best=0;
static int n; static long W;
static Item[] items;
static void dfs(int idx, long curW, long curV){
if(curW > W) return;
if(idx==n){ best = [Link](best, curV); return; }
double bound = curV;
long remW = W - curW;
for(int i=idx;i<n;i++){
if(items[i].w <= remW){ bound += items[i].v; remW -= items[i].w; }
else { bound += items[i].r * remW; break; }
}
if(bound <= best) return;
dfs(idx+1, curW + items[idx].w, curV + items[idx].v);
dfs(idx+1, curW, curV);
}
public static void main(String[] args) throws Exception{
FastScanner fs = new FastScanner([Link]);
n = [Link](); W = [Link]();
items = new Item[n];
for(int i=0;i<n;i++){ long w = [Link](), v = [Link](); items[i] = new Item(w,v); }
[Link](items);
dfs(0,0,0);
[Link](best);
}
 static class FastScanner { BufferedInputStream in; byte[] b = new byte[1<<16]; int p=0,len=0;
FastScanner(InputStream is){ in = new BufferedInputStream(is); } private int read() throws IOException {
if(p>=len){ len=[Link](b); p=0; if(len<=0) return -1; } return b[p++]; } int nextInt() throws IOException { i
s=1, x=0; while((c=read())<=32) if(c==-1) return Integer.MIN_VALUE; if(c=='-'){ s=-1; c=read(); } while(c>32){
x*10 + (c - '0'); c = read(); } return x*s; } long nextLong() throws IOException { int c; long x=0; int s=1;
while((c=read())<=32) if(c==-1) return Long.MIN_VALUE; if(c=='-'){ s=-1; c=read(); } while(c>32){ x = x*10 + (
'0'); c = read(); } return x*s; } }
}

10. NP-Complete: SAT, reductions, and subset-sum example (theory + reduction code snippet)
Problem: Understand NP-completeness and reduction mechanics. Provide a concrete small reduction: subset-sum to
partition or vice versa.
Approach: Explain reduction technique and provide small code that checks subset-sum via DP (not a reduction
solver).

Subset sum DP (decision): given n and array a[], and target S, can we choose subset summing to S?

Full Java program (DP):

import [Link].*;
import [Link].*;

public class SubsetSumDP {

public static void main(String[] args) throws Exception{
FastScanner fs = new FastScanner([Link]);
int n = [Link](); int S = [Link]();
int[] a = new int[n];
for(int i=0;i<n;i++) a[i]=[Link]();
boolean[] dp = new boolean[S+1]; dp[0]=true;
for(int x: a){
for(int s=S; s>=x; s--) if(dp[s-x]) dp[s]=true;
}
[Link](dp[S]?"YES":"NO");
}
static class FastScanner { BufferedInputStream in; byte[] b = new byte[1<<16]; int p=0,len=0;
FastScanner(InputStream is){ in = new BufferedInputStream(is); } private int read() throws IOException {
if(p>=len){ len=[Link](b); p=0; if(len<=0) return -1; } return b[p++]; } int nextInt() throws IOException { i
s=1, x=0; while((c=read())<=32) if(c==-1) return Integer.MIN_VALUE; if(c=='-'){ s=-1; c=read(); } while(c>32){
x*10 + (c - '0'); c = read(); } return x*s; } }
}

11. Clique / Vertex Cover reductions + example (theory + small verifier)

Problem: Show how Clique and Vertex Cover are complements and how to reduce between them.
Approach: Provide explanation and a small Java checker that verifies a given set is a vertex cover or clique.

Java verifier for given set:

import [Link].*;
import [Link].*;

public class CliqueVCVerifier {

public static void main(String[] args) throws Exception{
FastScanner fs = new FastScanner([Link]);
int n = [Link](), m = [Link]();
boolean[][] adj = new boolean[n][n];
for(int i=0;i<m;i++){ int u=[Link]()-1, v=[Link]()-1; adj[u][v]=adj[v][u]=true; }
int q = [Link]();
StringBuilder sb = new StringBuilder();
while(q-- > 0){
int type = [Link]();
int k = [Link]();
int[] vs = new int[k];
for(int i=0;i<k;i++) vs[i]=[Link]()-1;
boolean ok = true;
if(type==1){ // clique: all pairs connected
for(int i=0;i<k && ok;i++) for(int j=i+1;j<k;j++) if(!adj[vs[i]][vs[j]]){ ok=false; break; }
} else { // vertex cover: every edge has at least one endpoint in set
boolean[] in = new boolean[n];
for(int v:vs) in[v]=true;
for(int i=0;i<n && ok;i++) for(int j=i+1;j<n;j++) if(adj[i][j] && !in[i] && !in[j]){ ok=false;
break; }
}
[Link](ok?"YES":"NO").append('\n');
}
 [Link]([Link]());
}
static class FastScanner { BufferedInputStream in; byte[] b = new byte[1<<16]; int p=0,len=0;
FastScanner(InputStream is){ in = new BufferedInputStream(is); } private int read() throws IOException {
if(p>=len){ len=[Link](b); p=0; if(len<=0) return -1; } return b[p++]; } int nextInt() throws IOException { i
s=1, x=0; while((c=read())<=32) if(c==-1) return Integer.MIN_VALUE; if(c=='-'){ s=-1; c=read(); } while(c>32){
x*10 + (c - '0'); c = read(); } return x*s; } }
}

12. Practical heuristics for NP-hard problems (local search, approximation) - Java templates
Problem: Provide templates for hill-climbing / simulated annealing / greedy approximation for problems like TS
Approach: Present a simple 2-opt local search template for TSP.

2-opt local search Java template:

import [Link].*;
import [Link].*;

public class TSP2Opt {

static double dist(int[] a, int[] b){ double dx=a[0]-b[0], dy=a[1]-b[1]; return [Link](dx,dy); }
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader([Link]));
int n = [Link]([Link]().trim());
int[][] pts = new int[n][2];
for(int i=0;i<n;i++){ StringTokenizer st = new StringTokenizer([Link]());
pts[i][0]=[Link]([Link]()); pts[i][1]=[Link]([Link]()); }
int[] tour = new int[n];
for(int i=0;i<n;i++) tour[i]=i;
boolean improved=true;
while(improved){
improved=false;
for(int i=0;i<n-1;i++) for(int j=i+2;j<n;j++){
int a = tour[i], b = tour[(i+1)%n], c = tour[j], d = tour[(j+1)%n];
double before = dist(pts[a], pts[b]) + dist(pts[c], pts[d]);
double after = dist(pts[a], pts[c]) + dist(pts[b], pts[d]);
if(after + 1e-9 < before){
for(int l=0, r=j-(i+1); l<r; l++, r--) { int tmp = tour[i+1+l]; tour[i+1+l] = tour[j-l];
tour[j-l] = tmp; }
improved=true;
}
}
}
double total=0;
for(int i=0;i<n;i++) total += dist(pts[tour[i]], pts[tour[(i+1)%n]]);
[Link](total);
}
}