Warning

# Basic BFS and derived codes

#include <stdio.h>
#include <vector>
#include <queue>

using namespace std;

// Graph representation
int N, M;
vector<vector<int> > edge;

scanf( "%d%d", &N, &M );
edge.resize( N, vector<int>(0) );

int n1, n2;
for( int i = 0; i < M; i++ ) {
scanf( "%d%d", &n1, &n2 );
edge[n1].push_back( n2 );  // add edge
edge[n2].push_back( n1 );  // add edge
}
}

// print Graph, may help in debugging (sometimes greatly!)
void prGr(){
for( int i = 0; i < N; i++ ){
printf( "%d _", i );
for( int j = 0; j < edge[i].size(); j++ )
printf( " %d", edge[i][j] );
printf( "\n" );
}
}

/*
Example methods based on BFS.
All methods work in O(|E|) time,
however, they are a mere concept illustration
a therefore might be far from optimized.
*/

// --------------------------------------------------------------

void BFS( int start ){
std::queue< int > q;
std::vector< bool > fresh( N, true );
q.push( start );
fresh[start] = false;

int currn, neigh;
while( !q.empty() ){
currn = q.front(); q.pop();
for( int j = 0; j < edge[currn].size(); j++ ){
neigh = edge[currn][j];
if( fresh[neigh] ){
q.push( neigh );
fresh[neigh] = false;
printf(" BFS edge: %d -> %d\n", currn, neigh );
}
}
}
}

// --------------------------------------------------------------

bool isConnected(){
/**/  int start = 0;   // change #1
std::queue< int > q;
std::vector< bool > fresh( N, true );
q.push( start );
fresh[start] = false;

int currn, neigh;
while( !q.empty() ){
currn = q.front(); q.pop();
for( int j = 0; j < edge[currn].size(); j++ ){
neigh = edge[currn][j];
if( fresh[neigh] ){
q.push( neigh );
fresh[neigh] = false;
}
}
}

/**/  // change #2
for( int i = 0; i < N; i++ )
if( fresh[i] ) return false;
return true;
}

// --------------------------------------------------------------

bool isTree(){
/**/  int start = 0;   // change #1
std::queue< int > q;
/**/  std::vector< bool > pred( N, -1 ); // change #2
q.push( start );

int currn, neigh;
while( !q.empty() ){
currn = q.front(); q.pop();
for( int j = 0; j < edge[currn].size(); j++ ){
neigh = edge[currn][j];
/**/    if( pred[neigh] == -1 ){  // change #3, formal, is neigh fresh?
q.push( neigh );
pred[neigh] = currn;
}
/**/  else if( neigh != pred[currn] ) return false; // change #4
}
}

/**/  return true;  // change #5
}

// --------------------------------------------------------------

void distancesFrom( int start ){
std::queue< int > q;
std::vector< bool > fresh( N, true );
/**/  std::vector< int > dist( N, N+1 );  // change #1

q.push( start );
fresh[start] = false;
/**/  dist[start] = 0; // change #2

int currn, neigh;
while( !q.empty() ){
currn = q.front(); q.pop();
for( int j = 0; j < edge[currn].size(); j++ ){
neigh = edge[currn][j];
/**/ dist[neigh] = min(dist[neigh], 1+dist[currn]); // change #3
if( fresh[neigh] ){
q.push( neigh );
fresh[neigh] = false;
}
}
}

/**/ // change #4
for( int i = 0; i < N; i++ )
printf( "dist(%d %d) = %d\n", start, i, dist[i]);
}

// --------------------------------------------------------------

void shortestPathFromTo( int start, int target ){
std::queue< int > q;
std::vector< bool > fresh( N, true );
/**/ std::vector< int > pred( N, -1 ); // change #1

/**/  q.push( target );  // change #2  -- swap target and start
/**/  fresh[target] = false;

int currn, neigh;
while( !q.empty() ){
currn = q.front(); q.pop();
for( int j = 0; j < edge[currn].size(); j++ ){
neigh = edge[currn][j];
if( fresh[neigh] ){
q.push( neigh );
fresh[neigh] = false;
/**/    pred[neigh] = currn;  // change #3
}
}
}

/**/ // change #4  -- list the path
printf("shortest path: %d", start);
while( start != target ) {
start = pred[start];
printf( " -> %d", start);
}
printf( "\n" );
}

// --------------------------------------------------------------

int distanceFromTo( int start, int target ){
std::queue< int > q;
std::vector< bool > fresh( N, true );
/**/  std::vector< int > dist( N, N+1 );  // change #1

q.push( start );
fresh[start] = false;
/**/  dist[start] = 0; // change #2

int currn, neigh;
while( !q.empty() ){
currn = q.front(); q.pop();
for( int j = 0; j < edge[currn].size(); j++ ){
neigh = edge[currn][j];
/**/  dist[neigh] = min(dist[neigh], 1+dist[currn]); // change #3
/**/  if( neigh == target ) return dist[neigh]; // change #4
if( fresh[neigh] ){
q.push( neigh );
fresh[neigh] = false;
}
}
}
/**/ return -1; // change #5
}

// --------------------------------------------------------------

int mostDistantNode( int start ){
std::queue< int > q;
std::vector< bool > fresh( N, true );
/**/  std::vector< int > dist( N, N+1 );  // change #1

q.push( start );
fresh[start] = false;
/**/  dist[start] = 0; // change #2

int currn, neigh;
while( !q.empty() ){
currn = q.front(); q.pop();
for( int j = 0; j < edge[currn].size(); j++ ){
neigh = edge[currn][j];
/**/ dist[neigh] = min(dist[neigh], 1+dist[currn]); // change #3
if( fresh[neigh] ){
q.push( neigh );
fresh[neigh] = false;
}
}
}

/**/ // change #4
int maxdist = 0, maxdistnode = start;
for( int i = 0; i < N; i++ )
if( dist[i] > maxdist )
{ maxdist = dist[i]; maxdistnode = i;}
return maxdistnode;
}

// --------------------------------------------------------------

int treeDiameter() {
// just a demo(!), distanceFromTo performs additional redundant search.
int node1 = mostDistantNode( 0 ); // start anywhere
int node2 = mostDistantNode( node1 );
return distanceFromTo( node1, node2 );
}

// --------------------------------------------------------------

// Fill in yourself:
// bool isBipartite(){
// }

// --------------------------------------------------------------

int main() {

prGr();
BFS( 3 );
printf( "Connected: %s\n", isConnected()? "Yes" : "No" );
printf( "Is a tree: %s\n", isTree() ? "Yes" : "No" );
distancesFrom( 1 );
shortestPathFromTo( 4, 0 );
if( isTree() ) printf( "Tree Diameter: %d\n", treeDiameter() );

return 0;
}

# Dijkstra and MST codes

// MST and Dijkstra compared
// Note the sort method in Kruskal alg.

import java.util.*;
import java.io.*;

public class Solvers {

static void dijkstraNsquared(Graph g, int start,  final int [] dist, int [] pred ) {
int INF = Integer.MAX_VALUE;
int currnode = start, currdist, neigh;
boolean [] closed = new boolean [g.N];

for(int i = 0; i < g.N; i++) pred[i] = i;
Arrays.fill(dist, INF);
Arrays.fill(closed, false);
dist[start] = 0;

for( int i = 0; i < g.N; i++ ){
// find the closest node
currdist = INF;
for( int j = 0; j < g.N; j++)
if( !closed[j] && dist[j] < currdist ){
currdist = dist[j];
currnode = j;
}

// expand the closest node and close it
for( int j = 0; j < g.dg[currnode]; j++ ){
neigh = g.edge[currnode][j];
if( !closed[neigh] && ( dist[neigh] > dist[currnode] + g.w[currnode][j]) ) {
dist[neigh] = dist[currnode] + g.w[currnode][j];
pred[neigh] = currnode;
}
closed[currnode] = true;
}
} // for N steps
}

public static void dijkstraElogN(Graph g, int start, final int [] dist, int [] pred ) {
int currnode = start, currdist, neigh;
int INF = Integer.MAX_VALUE;
boolean [] closed = new boolean[g.N];

PriorityQueue <Integer> pq
= new PriorityQueue<Integer> (g.N,
new Comparator<Integer>() {
@Override
public int compare(Integer n1, Integer n2) {
if( dist[n1] < dist[n2] ) return -1;
if( dist[n1] > dist[n2] ) return 1;
return 0;
}
}
);

for(int i = 0; i < g.N; i++) pred[i] = i;
Arrays.fill(dist, INF);
Arrays.fill(closed, false);
dist[start] = 0;

for(int i = 0; i < g.N; i++) {
// take the closest node
while( closed[currnode = pq.poll()] == true );
// and expand it
for( int j = 0; j < g.dg[currnode]; j++ ){
neigh = g.edge[currnode][j];
if( !closed[neigh] && ( dist[neigh] > dist[currnode] + g.w[currnode][j]) ) {
dist[neigh] = dist[currnode] + g.w[currnode][j];
pred[neigh] = currnode;
}
closed[currnode] = true;
}
}
}

static void MST_Nsquared(Graph g, int start,  final int [] dist, int [] pred ) {
int INF = Integer.MAX_VALUE;
int currnode = start, currdist, neigh;
boolean [] closed = new boolean [g.N];

for(int i = 0; i < g.N; i++) pred[i] = i;
Arrays.fill(dist, INF);
Arrays.fill(closed, false);
dist[start] = 0;

for( int i = 0; i < g.N; i++ ){
// find the closest node
currdist = INF;
for( int j = 0; j < g.N; j++)
if( !closed[j] && dist[j] < currdist ){
currdist = dist[j];
currnode = j;
}

// expand the closest node and close it
for( int j = 0; j < g.dg[currnode]; j++ ){
neigh = g.edge[currnode][j];
if( !closed[neigh] && ( dist[neigh] > g.w[currnode][j]) ) {
dist[neigh] = g.w[currnode][j];
pred[neigh] = currnode;
}
closed[currnode] = true;
}
} // for N steps
}

public static void MST_ElogN(Graph g, int start, final int [] dist, int [] pred ) {
int currnode = start, currdist, neigh;
int INF = Integer.MAX_VALUE;
boolean [] closed = new boolean[g.N];

PriorityQueue <Integer> pq
= new PriorityQueue<Integer> (g.N,
new Comparator<Integer>() {
@Override
public int compare(Integer n1, Integer n2) {
if( dist[n1] < dist[n2] ) return -1;
if( dist[n1] > dist[n2] ) return 1;
return 0;
}
}
);

for(int i = 0; i < g.N; i++) pred[i] = i;
Arrays.fill(dist, INF);
Arrays.fill(closed, false);
dist[start] = 0;

for(int i = 0; i < g.N; i++) {
// take the closest node
while( closed[currnode = pq.poll()] == true );
// and expand it
for( int j = 0; j < g.dg[currnode]; j++ ){
neigh = g.edge[currnode][j];
if( !closed[neigh] && ( dist[neigh] > g.w[currnode][j]) ) {
dist[neigh] = g.w[currnode][j];
pred[neigh] = currnode;
}
closed[currnode] = true;
}
}
}

public static void MST_Kruskal(Graph g, int [] edgesMST ) {

// store edges in one arr and sort them
int [] edges = new int[g.M*3];
int k = 0;
for( int i = 0; i < g.N; i++ )
for( int j = 0; j < g.dg[i]; j++ ) {
if( i <  g.edge[i][j] ) {
edges[k++] = g.w[i][j];
edges[k++] = i;
edges[k++] = g.edge[i][j];
}
}
qSort3( edges, 0, edges.length-3 );

// construct the MST with UF
initUF( g.N );
int edgesCount = 0, set1, set2;
k = 0;
while( edgesCount < g.N-1 ){
set1 = UF_find(edges[k+1]); set2 = UF_find(edges[k+2]);
if( set1 != set2 ) {  // found an edge of MST
UF_union( set1, set2 );
edgesCount++;
edgesMST[edgesCount*2-2] = edges[k+1]; edgesMST[edgesCount*2-1] = edges[k+1] ;
}
k += 3;
}
}

public static void main( String[] args ) {
int [] p = {3, 10, 11, -3, 22, 25, 7, 33, 34, 4, 42, 43, 2, 56, 56 };
qSort3(p, 0, p.length-3);
list(p);

}

static void list (int [] a) {
for( int x : a )
System.out.printf("%2d ", x);
System.out.printf("\n");
}

static void qSort(double a[], int low, int high) {
int iL = low, iR = high;
double pivot = a[low];
double aux;
do {
while (a[iL] < pivot) iL++;
while (a[iR] > pivot) iR--;
if (iL < iR) {
//swap(a,iL, iR);
aux = a[iL]; a[iL] = a[iR]; a[iR] = aux;
iL++; iR--;
}
else
if (iL == iR) { iL++; iR--;}

} while( iL <= iR);

if (low < iR)  qSort(a, low, iR);
if (iL < high) qSort(a, iL, high);
}

// always points to i%3=0 elem which stores the key
static void qSort3(int a[], int low, int high) {
int iL = low, iR = high;
int pivot = a[low];
int aux;
do {
while (a[iL] < pivot) iL+=3;
while (a[iR] > pivot) iR-=3;
if (iL < iR) {
//swap(a,iL, iR);
for(int k = 0; k < 3; k++ )
{ aux = a[iL+k]; a[iL+k] = a[iR+k]; a[iR+k] = aux; }
iL+=3; iR-=3;
}
else
if (iL == iR) { iL+=3; iR-=3;}

} while( iL <= iR);

if (low < iR)  qSort3(a, low, iR);
if (iL < high) qSort3(a, iL, high);
}

// uf

static int [] sets;
static int [] sizes;
static int elem1;

static void initUF(int n) {
sets = new int [n];
sizes = new int [n];
for(int i = 0; i < n; i++) {
sets[i] = i;
sizes[i] = 1;
}
}

static void UF_union(int a, int b) {
//System.out.printf(" unioning %d %d \n", a, b);
if (sizes[b] > sizes[a]) {
sets[a] = b;
sizes[b] += sizes[a];
}
else {
sets[b] = a;
sizes[a] += sizes[b];
}
}

static int UF_find(int a) {
elem1 = a;
while (a != sets[a])
a = sets[a];
sets[elem1] = a;  // shorten the path
return a;
}

static void listSet(int a) {  // for debuggin purposes only
int finda = UF_find(a);
for(int i = 0; i < sets.length; i++)
if(UF_find(i) == finda)
System.out.printf("%d ", i);
System.out.printf("\n");
}

}

# Elementary DAG manipulation

#include <stdio.h>
#include <climits>
#include <vector>

using namespace std;

int N, E, NIL = -1;
vector<vector<int> > arc;
vector<vector<int> > wei;

vector<bool> visited;
vector<int> topSort;

scanf( "%d%d", &N, &E );
arc.resize( N, vector<int>(0) );
wei.resize( N, vector<int>(0) );
visited.resize( N );

int n1, n2, w;
for( int i = 0; i < E; i++ ) {
scanf( "%d%d%d", &n1, &n2, &w );
arc[n1].push_back( n2 );  // add directed arc
wei[n1].push_back( w );   // add arc weight
}
}

void prGr(){
for( int i = 0; i < N; i++ ){
printf( "%d _", i );
for( int j = 0; j < arc[i].size(); j++ )
printf( " %2d:%2d", arc[i][j], wei[i][j] );
printf( "\n" );
}
}

void DFS_rec( int node ){
visited[node] = true;
for( int j = 0; j < arc[node].size(); j++ )
if( !visited[arc[node][j]] )
DFS_rec( arc[node][j]);
topSort.push_back( node );
}

void DFS(){
std::fill(visited.begin(), visited.end(), false);
topSort.clear();

for( int start = 0; start < N; start++ )
if( !visited[start] )
DFS_rec( start );
}

int findIndexOfMax( std::vector<int> & v ){
int max = INT_MIN, imax = -1;
for( int i = 0; i < v.size(); i++ )
if( v[i] > max ) {
max = v[i];
imax = i;
}
return imax;
}

void printPath( std::vector<int> & path, int start ){
printf( "Longest path: \n" );
while( start != NIL ){
printf( " %d", start );
start = path[start];
}
printf( "\n" );
}

void longestPath() {
std::vector< int > pathNext( N, NIL );
std::vector< int > dist( N, 0 );

int currnode, neigh;
for( int i = 0; i < N; i++ ){ // progress in reverse top order
currnode = topSort[i];
for( int j = 0; j < arc[currnode].size(); j++ ){
neigh = arc[currnode][j];
if ( dist[currnode] < dist[neigh] + 1 ){
dist[currnode] = dist[neigh] + 1;
pathNext[currnode] = neigh;
}
}
}
int start = findIndexOfMax( dist );
printPath( pathNext, start );
}

void longestPathWeight() {
std::vector< int > pathNext( N, NIL );
std::vector< int > dist( N, 0 );

int currnode, neigh;
for( int i = 0; i < N; i++ ){ // progress in reverse top order
currnode = topSort[i];
for( int j = 0; j < arc[currnode].size(); j++ ){
neigh = arc[currnode][j];
if ( dist[currnode] < dist[neigh] + wei[currnode][j] ){
dist[currnode] = dist[neigh] + + wei[currnode][j];
pathNext[currnode] = neigh;
}
}
}
int start = findIndexOfMax( dist );
printPath( pathNext, start );
}

///////////////////////////   M A I N   /////////////////////////////////
int main() {

prGr();
DFS();
printArr( topSort );
longestPathWeight();
return 0;
}

/*
5 5
0 1 10
1 2 20
2 3 30
2 4 40
0 2 150
*/