HackerEarth Explosion problem solution

In this HackerEarth Explosion problem solution There are N cities connected through bidirectional roads and this network forms an tree. The country is very vulnerable to terrorist attacks which is very alarming. The defense sector was notified of a terrorist attack and now they want to protect cities by sending their troops since it has been too late they can't send troops to every city.

The defense sector and terrorists will make a move alternately and the defense sector will go first.

• Defense sector move: They will select a city that has not been chosen yet and send troops there.
• Terrorist move: They will select a city that has not been chosen yet and place a bomb there.

After all the cities have been selected an explosion will take place in which all the cities containing bomb and any city which has road to bomb containing city will be deteriorated. If any city exists which didn't deteriorate, the country is SAFE else UNSAFE.

Note that terrorists wants country to be unsafe while defence sector wants country to be safe so they place troops and bombs optimally.

HackerEarth Explosion problem solution.

#include<bits/stdc++.h>
using namespace std;
#define FIO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define mod 1000000007
#define endl "\n"
#define test ll t; cin>>t; while(t--)
typedef long long int ll;
string pr;
ll dfs(ll node,ll par,vector<ll>adj[]){
    ll dis=1;
    for(auto u:adj[node]){
        if(u==par) continue;
        dis-=dfs(u,node,adj);
    }
    if(dis<0 || (dis==1 && node==0)){
        pr="SAFE";
    }
    return dis;
}
int main() {
    FIO;
    test
    {
        ll n,l,r; cin>>n;
        vector<ll>adj[n];
        for(ll i=1;i<n;i++){
            cin>>l>>r; l--; r--;
            adj[l].push_back(r);
            adj[r].push_back(l);
        }
        pr="UNSAFE";
        dfs(0,-1,adj);
        cout<<pr<<endl;
    }
    return 0;
}

Second solution

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int MAX_N = 1e5 + 14;
vector<int> g[MAX_N];

int matching(int v = 0, int p = -1) {
    int need = 0;
    for (auto u : g[v]) {
        if (u == p)
            continue;
        int t = matching(u, v);
        if (t == -1)
            return -1;
        need += t == 0;
    }
    return need == 0 ? 0 : need == 1 ? 1 : -1;
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        fill(g, g + n, vector<int>());
        for (int i = 0; i < n - 1; ++i) {
            int v, u;
            cin >> v >> u;
            v--, u--;
            g[v].push_back(u);
            g[u].push_back(v);
        }
        cout << (matching() == 1 ? "UNSAFE\n" : "SAFE\n");
    }
}