ds 203 online 2

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 27;

int N, E;
vector<pair<int, int> > adj[MAXN];
int parent[MAXN];
bool vis[MAXN];

void init()
{
    for (int i = 0; i < MAXN; i++)
    {
        adj[i].clear();
        vis[i] = false;
        parent[i] = -1;
    }
}


///complexity O(V+E)
void bfs(int src)
{
    queue<int> q;
    q.push(src);
    vis[src] = true;
    while(!q.empty())  /// total V nodes will be pushed in the queue..it takes O(V) complexity. Again for each node only their adjecent will be checked. Thus total complexity O(V+E)
    {
        int u = q.front();
        q.pop();

        ///printing the char representation of the current node
        char node = (char)(u + 65);
        cout << node << " ";
        for(auto i : adj[u])
        {
            int v = i.second;
            if (!vis[v])
            {
                vis[v] = true;
                parent[v] = u;
                q.push(v);
            }
        }
    }
}

void dfs(int src)
{
    cout << (char)(src + 65) << " ";
    vis[src] = true;
    for(auto i : adj[src])
    {
        int v = i.second;
        if(!vis[v])
        {
            parent[v] = src;
            dfs(v);
        }
    }
}

void PrintPath(int x)
{
    if(parent[x] == -1) return;
    PrintPath(parent[x]);
    cout << " -> " <<(char) (x+65) ;
}

int main()
{
    init();
    cin >> N >> E;
    for (int i = 0; i < E; i++)
    {
        char x, y;
        int w;
        cin >> x >> y >> w;
        int u = (int)x - 65;
        int v = (int)y - 65;
        adj[u].emplace_back(make_pair(w, v));
        adj[v].emplace_back(make_pair(w, u));
    }

    /// each node will take O(VlogV) times.. for all V nodes, it takes O(V^2longV) complexity to sort the whole adj list
    for(int i = 0; i < 20; i++) sort(adj[i].begin(), adj[i].end());


    char nodeX = 'E', nodeY = 'S';
    int src = (int)nodeX - 65, des = (int)nodeY - 65; /// convert nodeX and nodeY to numerical value

    /// BFS here
    cout << "**BFS**\n";
    cout << "Exploration Order for bfs: ";
    bfs(src);
    cout << "\n";
    cout << "From " << nodeX << " to " << nodeY << " path: " << nodeX;
    PrintPath(des);
    cout << "\n\n";

    /// clear vis and parent array
    memset(vis, 0, sizeof(vis));
    memset(parent, -1, sizeof(parent));

    /// DFS here
    cout << "**DFS**\n";
    cout << "Exploration Order for dfs: ";
    dfs(src);
    cout << "\n";
    cout << "From " << nodeX << " to " << nodeY << " path: " << nodeX;
    PrintPath(des);
    cout << "\n\n";
}


/*
19 28
A I 5
A E 1
A B 8
B D 8
B G 1
G H 0
G F 9
H D 5
C D 2
E F 8
C F 4
C P 3
F P 7
E R 9
R N 3
R O 4
R T 2
P T 6
T L 0
T Q 5
T K 5
N K 7
L S 7
Q S 6
Q O 4
K O 9
Q M 9
M S 8
*/