[Spoj] ONEZERO - Ones and zeros

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : ONEZERO - Ones and zeros
Source            : Spoj
Category          : Graph Theory
Algorithm         : BFS
Verdict           : Accepted

#include "bits/stdc++.h"
 
using namespace std;
 
static const int maxn = 20000 + 5;
 
int father[maxn], used[maxn], vis[maxn];
 
inline void bfs(int n)
{
    for (int i = 0; i < maxn; i++) father[i] = used[i] = -1, vis[i] = 0;
    int r = 1 % n;
    father[r] = -1;
    used[r] = 1;
    vis[r] = 1;
    queue <int> PQ;
    PQ.emplace(r);
    while (!PQ.empty() && !vis[0])
    {
        int u = PQ.front(); PQ.pop();
        int rr = (u * 10) % n;
        if (!vis[rr])
        {
            vis[rr] = 1;
            father[rr] = u;
            used[rr] = 0;
            PQ.emplace(rr);
        }
        if (vis[0]) break;
        rr = (u * 10 + 1) % n;
        if (!vis[rr])
        {
            vis[rr] = 1;
            father[rr] = u;
            used[rr] = 1;
            PQ.emplace(rr);
        }
        if (vis[0]) break;
    }
    string s = "";
    int v = 0;
    do {
        s += ('0' + used[v]);
        v = father[v];
    } while (v != -1);
    reverse(s.begin(), s.end());
    cout << s << endl;
}
 
int main()
{
    int tc;
    cin >> tc;
    for (int tcase = 1; tcase <= tc; tcase++) 
    {
        int n;
        cin >> n;
        bfs(n);
    }
}