[UVA] 10507 - Waking up brain

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : 10507 - Waking up brain
Source            : UVA Online Judge
Category          : Graph Theory
Algorithm         : bfs
Verdict           : Accepted

#include "bits/stdc++.h"  
  
using namespace std;  
  
#define vi                vector <int>  
#define em                emplace_back  
  
static const int maxn = 30;  
  
vi graph[maxn];  
int on[maxn], dis[maxn];  
int tnode, tedge;  
char s[5];  
set <int> used[maxn];  
  
void init()  
{  
    for (int i = 0; i < maxn; i++)  
    {  
        graph[i].clear();  
        on[i] = 0;  
        used[i].clear();  
    }  
}  
  
int toint(char ch)  
{  
    return ch - 'A' + 1;  
}  
  
int bfs(int x, int y, int z)  
{  
    on[x] = on[y] = on[z] = 1;  
    queue <int> PQ;  
    PQ.emplace(x);  
    PQ.emplace(y);  
    PQ.emplace(z);  
    dis[x] = dis[y] = dis[z] = 0;  
    int maxdis = 0;  
    int vis = 3;  
    while (!PQ.empty())  
    {  
        int u = PQ.front(); PQ.pop();  
        for (int v : graph[u])  
        {  
            if (on[v]) continue;  
            used[v].emplace(u);  
            if (used[v].size() == 3)  
            {  
                dis[v] = dis[u] + 1;  
                if (dis[v] > maxdis) maxdis = dis[v];  
                on[v] = 1;  
                vis++;  
                PQ.emplace(v);  
            }  
        }  
    }  
    if (vis < tnode) return -1;  
    return maxdis;  
}  
  
int main()  
{  
    while (scanf("%d", &tnode) == 1)  
    {  
        init();  
        scanf("%d", &tedge);  
        scanf("%s", s);  
        int x = toint(s[0]);  
        int y = toint(s[1]);  
        int z = toint(s[2]);  
        for (int e = 1; e <= tedge; e++)  
        {  
            scanf("%s", s);  
            int u = toint(s[0]);  
            int v = toint(s[1]);  
            graph[u].em(v);  
            graph[v].em(u);  
        }  
        int year = bfs(x, y, z);  
        if (year == -1) printf("THIS BRAIN NEVER WAKES UP\n");  
        else printf("WAKE UP IN, %d, YEARS\n", year);  
    }  
}