#include <iostream>

#define MAX_N 10

int A[MAX_N];

void selectSort(int k){

    if(k==MAX_N-1) return;

    int min = 100000;

    int minIdx;

    for(int i=k;i<MAX_N;i++){

        if(A[i] < min){

            min = A[i];

            minIdx = i;

        }

    }

    int temp = A[k];

    A[k] = A[minIdx];

    A[minIdx] = temp;

    selectSort(k+1);

}

int main(){

    A[0]= 8;

    A[1]= 5;

    A[2]= 1;

    A[3]= 2;

    A[4]= 1;

    A[5]= 4;

    A[6]= 3;

    A[7]= 2;

    A[8]= 9;

    A[9]= 15;

    selectSort(0);

    return 0;

}

#include <iostream>

#define MAX_N 1000

using namespace std;

//map의 0 에 사이즈를 저장한 인접배열

int map[MAX_N+1][MAX_N+1];

int visit[MAX_N+1];

void DFS_Recursive(int n){

    cout << " " << n;

    visit [n] = 1;

    for(int i=1;i<=map[n][0];i++){

        if(!visit[map[n][i]])

        DFS_Recursive(map[n][i]);

    }

}

int stack[MAX_N+1];

int stack_p =0 ;

void DFS_Stack(int v){

    stack[stack_p++] = v;

    while (stack_p > 0){

        v = stack[--stack_p];

        if(!visit[v]){

            cout << " " << v;

            visit[v] = 1;

            for(int w=1;w<=map[v][0];w++){

                if(!visit[map[v][w]])

                    stack[stack_p++] = map[v][w];

            }

        }

    }

}

int queue_p_begin = 0;

int queue_p_end = 0;

int queue[MAX_N+1];

void BFS_Queue(int v){

    queue_p_begin = 0;

    queue[queue_p_begin] = v;

    queue_p_end = 1;

    while (queue_p_begin < queue_p_end){

        v = queue[queue_p_begin++];

        if(!visit[v]){

            cout << " " << v;

            visit[v] = 1;

            for(int w=1;w<=map[v][0];w++){

                if(!visit[map[v][w]])

                    queue[queue_p_end++] = map[v][w];

            }

        }

    }

}

int main(){

    int T, test_case;

    int N;

    int src,dst;

    freopen ( "sample_input.txt", "r", stdin );

    cin >> T;

    for(test_case = 1; test_case <= T; test_case++){

        for(int i=0;i<=MAX_N; i++){

            map[i][0] = 0;

        }

        cin >> N;

        cout << "Graph" <<endl;

        for(int i=0;i<N;i++){

            cin >> src &\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0gt;> dst;

            map[src][0]++;

            map[src][map[src][0]] = dst;

            cout << src << " -> "<<dst << endl;

        }

        for(int i=0;i<=MAX_N; i++) visit[i] = 0;

        //BFS(Queue)

        cout << "BFS(Queue):";

        BFS_Queue(1);

        cout << endl;

        //DFS(Recursive)

        cout << "DFS(Recu.):";

        for(int i=0;i<=MAX_N; i++) visit[i] = 0;

        DFS_Recursive(1);

        cout << endl;

        //DFS(Stack)

        cout << "DFS(Stack):";

        for(int i=0;i<=MAX_N; i++) visit[i] = 0;

        stack_p =0;

        DFS_Stack(1);

        cout << endl;

        //Dijkstra

    }

    return 0;

}

#include <iostream>

#define MAX_N 1000

using namespace std;

//adjacent array version

//A의 0 에 사이즈를 저장한 인접배열

int A[MAX_N+1][MAX_N+1];

int maxNode;

int D[MAX_N+1]; // distance

int U[MAX_N+1]; // selected vertex set

int UN=0;

void dijkstra(int s){

    U[s] = 1;

    cout << (char)(s+'a') <<" ";

    UN++;

    //0 에서 해당 정점까지의 거리를 초기값으로 입력한다.

    for(int i=0;i<=maxNode;i++){

        D[i] = A[s][i];

    }

    while(UN<=maxNode){

        //이미 선택되지 않은 정점중 가장 가까운 것을 찾는다.

        int min = 1000;

        int minIdx ;

        for (int i=0;i<=maxNode;i++){

            if( i!=s && !U[i] && min > D[i] && D[i]!=-1){

                minIdx = i;

                min = D[i];

            }

        }

        U[minIdx] = 1;

        UN++;

        cout << (char)(minIdx + 'a') <<" ";

        if(UN>maxNode){ break;} //it is really needed??

        for(int i=0;i<=maxNode;i++){

            if(A[minIdx][i]!=-1){

                //i 로 바로갈까 아니면 다른데 들러서 갈까?

                D[i] = (D[i] !=-1 && (D[i] < (D[minIdx] + A[minIdx][i])))?D[i]:(D[minIdx] + A[minIdx][i]);

            }

        }

    }

    //for(int i=0;i<=maxNode;i++){

    //    if(U[i]==0){

    //        cout << (char)(i + 'a') ;

    //    }

    //}

    cout << endl;

}

int main(){

    int T, test_case;

    int N;

    char src,dst;

    int weight;

    freopen ( "sample_input.txt", "r", stdin );

    cin >> T;

    for(test_case = 1; test_case <= T; test_case++){

        for(int i=0;i<=MAX_N; i++){

            for (int j=0;j<=MAX_N;j++){

                if(i==j)

   \0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0                 A[i][j] = 0;

                else

                    A[i][j] =-1; // dijkstra 는 - 값을 다루지 않는다.

            }

        }

        cin >> N;

        cout << "Graph" <<endl;

        maxNode =0;

        for(int i=0;i<N;i++){

            cin >> src >> dst >> weight;

            A[src-'a'][dst-'a'] = weight;

            if (src-'a'> maxNode){

                maxNode = src-'a';

            }

            if (dst-'a'> maxNode){

                maxNode = dst -'a';

            }

        }

        for(int i=0;i<=maxNode;i++){

        for(int j=0;j<=maxNode;j++)

            cout << A[i][j] <<" ";

        cout << endl;

        }

        //Aijkstra

        dijkstra(0);

    }

    return 0;

}

//String quick sort

#include <iostream>

#include <stdio.h>

#define MAX_N 6

#define SWAP(a, b) do { a ^= b; b ^= a; a ^= b; } while ( 0 )

using namespace std;

inline int my_strlen(const char* str){int n=0;for(n=0;str[n]!='\0';n++);return n;}

int my_strcmp(const char* str1, const char* str2){

    if(str1[0]=='\0'|| str2[0]=='\0') return str2[0] - str1[0];

    int diff=0;

    for(int n=0;str1[n]!='\0' && str2[n]!='\0';n++){

        diff = str2[n] - str1[n];

        if(diff!=0) return diff;

    }

    return diff;

}

int getLCP(const char* str1, const char* str2){

    int n;

    for(n=0;str1[n]!='\0' && str2[n]!='\0';n++){

        if(str2[n] - str1[n]) break;

    }

    return n;

}

//adjacent list

int N;

char str[MAX_N + 1];

int suffixArray[MAX_N + 1];

int LCP[MAX_N + 1];

void quick_sort(int first, int last){

    int pivot, j, temp, i;

    if(first < last){

        pivot = first;

        i = first;

        j = last;

        while ( i < j){

            while (my_strcmp((char*)(str + suffixArray[i]),(char*)(str + suffixArray[pivot])) >= 0 && i<last) i++;

            while (my_strcmp((char*)(str + suffixArray[j]),(char*)(str + suffixArray[pivot])) < 0) j--;

            if(i<j){

                temp = suffixArray[i];

                suffixArray[i] = suffixArray[j];

                suffixArray[j] = temp;

            }

        }

        temp = suffixArray[pivot];

        suffixArray[pivot] = suffixArray[j];

        suffixArray[j] = temp;

        quick_sort(first,j-1);

        quick_sort(j+1,last);

    }

}

void calculateLCP(){

    LCP[0] = 0;

    for(int i=1;i<=N;i++){

        LCP[i] = getLCP((char*)(str+suffixArray[i - 1]), (char*)(str+suffixArray[i]));

    }

}

int main(){

    int T, test_case;

    freopen ( "sample_input.txt", "r", stdin );

    cin >> T;

    for(test_case = 1; test_case <= T; test_case++){

        //initialization

        //input

       \0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0; cin >> str;

        cout << "["<<str<<"]" << endl;

        N = my_strlen(str);

        str[N] = '$';

        str[N+1] = '\0';

        //print suffix

        cout << "1. Suffix list" << endl;

        for(int i=0;i<=N;i++){

            suffixArray[i] = i;

            cout << "\t" << (i + 1) << " " << (char*)(str+suffixArray[i]) << endl;

        }

        quick_sort(0,N);

        cout << "2. Suffix array" << endl;

        for(int i=0;i<=N;i++){

            cout << "\t" << (i + 1) << " " << (char*)(str+suffixArray[i]) << endl;

        }

        calculateLCP();

        cout << "3. Suffix array and LCP" << endl;

        for(int i=0;i<=N;i++){

            cout << "\t" << (i + 1) << " "<< LCP[i] <<" " << (char*)(str+suffixArray[i]) << endl;

        }

    }

    return 0;

}