SPOJ: AKBAR - Akbar, The great

I am trying to solve this problem using BFS. I am not sure what I am doing wrong. Here is the code that I have written: lhUVGD - Online C++0x Compiler & Debugging Tool - Ideone.com

It would be great if someone can help me out.
Thanks!

I am to getting WA in this Question, Please help!!!
problem = AKBAR - Akbar , The great
My Solution → My Submission

please Help!!!

@bishen28 Your code fails for the following simple graph.
1
4 4 1
1 2
2 3
3 4
4 1
1 4

I checked your code, the way you’ve implemented BFS is wrong, in particular, the line

int node = q.front();q.pop();S--;
is problematic. 

Decrmenting S for every node in the queue is wrong
What you can change is that each node that goes into queue is a pair, the first one is the node id and the second is strenght left.
So the code would be like this

void  BFS(int s,vector<vector<int>> &adj_list,vector<int> &Protected, int S, vector<bool> & visited){
       Protected[s]++;
       queue<pair<int, int>> q;
       visited[s] = true;
       q.push({s, S});
       while(!q.empty()) {
          int node = q.front().first;
					int strength_left = q.front().second;
					q.pop();
					if (strength_left <= 0) {
						continue;
					}
          for(auto adj_node:adj_list[node]){ 
            if(visited[adj_node]==false){ 
                   Protected[adj_node]++;
                   q.push({adj_node, strength_left-1});
                   visited[adj_node] = true; 
            }    
          }
       }
}

After making the above changes, you code is giving TLE. I would suggest that you use multi source BFS for this problem and whenever protected[i] gets > 1, you stop.

Check my below AC code

// https://www.spoj.com/problems/AKBAR/
#include <bits/stdc++.h>
// Common file
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 

using namespace __gnu_pbds;
using namespace std;


using ll = long long;
using pi = pair<int, int>;
using ti = tuple<int, int, int>;
using tl = tuple<ll, ll, ll>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pl = pair<ll, ll>;
using vi = vector<int>;
using vl =  vector<ll>;
using vpi = vector<pi>;
using vpil = vector<pil>;
using vpli = vector<pli>;
using vpl = vector<pl>;
using vti = vector<ti>;
using vtl = vector<tl>;
using vvi = vector<vi>;
using vvl = vector<vl>;
using vvpi = vector<vpi>;
using vvpil = vector<vpil>;
using vvpli = vector<vpli>;
using vvpl = vector<vpl>;
using vvti = vector<vti>;
using vvtl = vector<vtl>;

using oset =  tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>;

using omset =  tree<pair<int,int>, null_type, less<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update>;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int INF = INT_MAX;
const ll LINF = LLONG_MAX;
const int MOD = 1000000000 + 7;

#define setbits(n) __builtin_popcount(n)
/* #define len(x) (int)size(x) */

/* void setIO(string name = "") { */
/* 	ios_base::sync_with_stdio(false); */
/* 	cin.tie(nullptr); */
/* 	if (len(name)) { */
/* 		ignore = freopen((name + ".in").c_str(), "r", stdin); */
/* 		ignore = freopen((name + ".out").c_str(), "w", stdout); */
/* 	} */
/* } */
const int N = (int) 1e6;
vi g[N+1];
// visited[i] Stores the root node of the bfs tree of which node i is a part
int visited[N+1];
vpi src;

bool bfs() {
	queue<pi> q;
	int sz = (int) src.size();
	for (int i = 0; i < sz; i++) {
		q.push({src[i].first, src[i].second});
		visited[src[i].first] = src[i].first;
	}
	while (!q.empty()) {
		int u = q.front().first;
		int strength = q.front().second;
		assert(visited[u]);
		q.pop();
		if (strength <= 0) {
			continue;
		}
		for (int v : g[u]) {
			if (!visited[v]) {
				visited[v] = visited[u];
				q.push({v, strength-1});
			} else {
				if (visited[v] == visited[u]) {
					continue;
				}
				assert(visited[v] != visited[u]);
				return false;
			}
		}
	}
	return true;
}
void reset(int n) {
	for (int i = 1; i <= n; i++) {
		g[i].clear();
		visited[i] = 0;
	}
	src.clear();
}
int main() {
	/* setIO(); */
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int T;
	cin >> T;
	while (T--) {
		int n, r, m;
		cin >> n >> r >> m;
		for (int i = 0; i < r; i++) {
			int u, v;
			cin >> u >> v;
			g[u].emplace_back(v);
			g[v].emplace_back(u);
		}
		/* for (int i = 1; i <= n; i++) { */
		/* 	cout << i << "\n"; */
		/* 	for (int v : g[i]) { */
		/* 		cout << v << " "; */
		/* 	} */
		/* 	cout << endl; */
		/* } */
		/* cout << endl; */
		for (int i = 0; i < m; i++) {
			int k, s;
			cin >> k >> s;
			src.emplace_back(k, s);
		}
		bool flag = bfs();
		if (!flag) {
			cout << "No\n";
		} else {
			bool ans = true;
			for (int i = 1; i <= n; i++) {
				if (!visited[i]) {
					ans = false;
					break;
				}
			}
			if (ans) {
				cout << "Yes\n";
			} else {
				cout << "No\n";
			}
		}
		reset(n);
	}
	return 0;
}

And here is your own AC code with few changes, you can check the changes by using diff, something like vim -d new_code.cc old_code.cc

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


bool  BFS(int s,vector<vector<int>> &adj_list,vector<int> &Protected, int S, vector<bool> & visited){
	Protected[s]++;
	if (Protected[s] > 1) {
		return false;
	}
	queue<pair<int, int>> q;
	visited[s] = true;
	q.push({s, S});
	while(!q.empty()) {
		int node = q.front().first;
		int strength_left = q.front().second;
		q.pop();
		if (strength_left <= 0) {
			continue;
		}
		for(auto adj_node:adj_list[node]){ 
			if(visited[adj_node]==false){ 
				Protected[adj_node]++;
				q.push({adj_node, strength_left-1});
				visited[adj_node] = true; 
			}    
		}
	}
	return true;
}

void solve(){
   int n,r,m;cin>>n>>r>>m;
   vector<vector<int>> adj_list(n+1);
   vector<int> Protected(n+1,0);
   vector<bool> visited(n+1,false);
   for(int i=0;i<r;i++){
    int A,B;cin>>A>>B;
    adj_list[A].push_back(B);
    adj_list[B].push_back(A);
   }
   vector<int> strength(n+1,-1);
   for(int i=0;i<m;i++){
       int K,S;cin>>K>>S;
       strength[K] = S;
   }
	 bool flag = true;
	 for(int i=1;i<=n;i++){
		 if(strength[i] >= 0) {
			 flag = BFS(i,adj_list,Protected,strength[i],visited);
			 if (!flag) {
				 break;
			 }
		 }
		 /* for(int s=0;s<=n;s++) visited[s] = false; */
	 }
	 /* for(int i=1;i<=n;i++){ */
		 /* cout << Protected[i] << "\n"; */
	 /* } */
	 if (!flag) {
		 cout << "No\n";
		 return;
	 } else {
		 for(int i=1;i<=n;i++){
			 if(visited[i] == false) {
				 flag = false;
				 break;
			 }
		 }
	 }
	 if (flag) {
		 cout << "Yes\n";
	 } else {
		 cout << "No\n";
	 }
   return;
}


int main(){
    ios_base::sync_with_stdio(0) ;
    cin.tie(0) ; cout.tie(0) ;
    cout.precision(20);

    int T;cin>>T;
    while(T--){
     solve();
		 /* if(T)cout << "\n"; */
    }
    return 0;
}