UVA 336 - A Node Too Far + 762 - We Ship Cheap

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

#define endl     "\n"
#define ll       long long
#define PI       acos(-1.0)
#define test     cout<<"\n****\n"
#define LCM(a,b) ((a/__gcd(a,b))*b)
#define READ(f)  freopen(f, "r", stdin)
#define WRITE(f) freopen(f, "w", stdout)
#define precise  fixed(cout);cout<<setprecision(20)
#define fast     ios_base :: sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)

map<int,vector<int>>graph;
map<int,int>visited;

int BFS(int root,int ttl){

    visited[root] = 0;
    queue<int> que;
    que.push(root);

    while (!que.empty()){

        int parent = que.front();
        que.pop();
        for(int i=0;i<graph[parent].size();i++){
            int child = graph[parent][i];
            if(child!=root) {
                if (visited[child] == 0) {

                    visited[child] = visited[parent] + 1;
                    que.push(child);
                }
            }
        }
    }

    int count = 0;
    for(auto it=visited.begin();it!=visited.end();it++){

        if(it->second>ttl){
            count++;
        } else if(it->second==0 && it->first!=root){
            count++;
        }
    }

    return count + (graph.size()-visited.size());
}

int main(){

    fast;
    int edge;
    int casee = 1;
    while (cin>>edge && edge){

        while (edge--){
            int from,to;
            cin>>from>>to;
            graph[from].push_back(to);
            graph[to].push_back(from);
        }

        int root,ttl;
        while (cin>>root>>ttl){
            if(root==0 && ttl==0){
                break;
            }
            cout<<"Case "<<casee<<": "<<BFS(root,ttl)<<" nodes not reachable from node "<<root<<" with TTL = "<<ttl<<".\n";
            visited.clear();
            casee++;
        }

        graph.clear();

    }

    return 0;
}


***********************************************************************************************
*************************************762 - We Ship Cheap***************************************



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

#define endl     "\n"
#define ll       long long
#define PI       acos(-1.0)
#define test     cout<<"\n****\n"
#define LCM(a,b) ((a/__gcd(a,b))*b)
#define READ(f)  freopen(f, "r", stdin)
#define WRITE(f) freopen(f, "w", stdout)
#define precise  fixed(cout);cout<<setprecision(20)
#define fast     ios_base :: sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)


map<string,vector<string>> graph;
map<string,bool>visited;
map<string,string> previous;

bool BFS(string from,string to){

    string root = from;
    visited[from] = true;

    queue<string>que;
    que.push(root);

    while (!que.empty()){

        string parent = que.front();
        que.pop();

        for(int i=0;i<graph[parent].size();i++){
            string child = graph[parent][i];

            if(!visited[child]) {
                visited[child] = true;
                previous[child] = parent;
                if(child==to){
                    return  true;
                }
                que.push(child);
            }
        }
    }

    return false;
}


void path(string from,string to){

    if(from==to){
        return;
    }
    path(from,previous[to]);
    cout<<previous[to]<<" "<<to<<endl;
}

int main(){

    int n;
    bool flag = false;
    while(cin>>n){

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

            string edge1,edge2;
            cin>>edge1>>edge2;
            graph[edge1].push_back(edge2);
            graph[edge2].push_back(edge1);
        }

        string from,to;
        cin>>from>>to;

        if(!flag) {
            flag = true;
        } else{
            cout<<endl;
        }

            if (BFS(from, to)) {
                path(from, to);
            } else {
                cout << "No route\n";
            }


        graph.clear();
        visited.clear();
        previous.clear();

    }
    return 0;
}