Warning
This page is located in archive. Go to the latest version of this course pages. Go the latest version of this page.

Table of Contents

Type code online

http://www.tutorialspoint.com/compile_cpp11_online.php

Basic BFS and derived codes

#include <stdio.h>
#include <vector>
#include <queue>
 
using namespace std;
 
// Graph representation
int N, M;
vector<vector<int> > edge;
 
 
void readGr(){
	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() {
 
  readGr();
  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;
            }
          }
      );
 
  pq.add(start);
  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;
        pq.add(neigh);
      }
     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;
            }
          }
      );
 
  pq.add(start);
  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;
        pq.add(neigh);
      }
     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;
 
 
void readGr(){
  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() {
 
  readGr();
  prGr();
  DFS();
  printArr( topSort );
  longestPathWeight();
    return 0;
}
 
/*
5 5
0 1 10
1 2 20
2 3 30
2 4 40
0 2 150
*/

courses/a4b36acm1/2016_zs/code.txt · Last modified: 2018/10/03 03:51 (external edit)