Type code online
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
*/