Search
http://www.tutorialspoint.com/compile_cpp11_online.php
#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; }
// 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"); } }
#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 */