HackerEarth Separate paths problem solution

In this HackerEarth Separate paths problem solution, You are given a directed graph that contains N nodes (numbered from 1 to N) and M edges.

A valid path is a path that starts from a node that does not contain any edges that are directed towards it. That is, the value of Indegree of node is 0. This path can also contain only one node in it. That is, the paths of length 0 are also valid paths but they must still follow the main condition that the starting node (in this case the only node) should not contain any edges that are directed towards it.

You are required to calculate the number of unordered pair of nodes such that there exist two valid paths that end at these nodes. These two paths should not contain any node in common.

HackerEarth Separate paths problem solution.

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

#define ll long long
#define endl "n"
#define PB push_back
#define MP make_pair
#define fr(i,n) for(i=1;i<=n;i++)

typedef vector<ll> vl;
const ll N = 510;

vl v[N],v1;
ll vis[N], cur, deg[N], ans[N][N];

void dfs(ll s)
{
    vis[s]=1;
    for(auto it:v[s])
        if(vis[it]==0 && it!=cur)
            dfs(it);
    return;
}

int main()
{
    ll t,i,j,n,m,x,y,cnt;
    cin>>t;
    while(t--)
    {
        cin>>n>>m;
        cur=-1;
        for(i=0;i<=n;i++) v[i].clear();
        fr(i,n) deg[i]=0;
        fr(i,n) fr(j,n) ans[i][j]=1;

        fr(i,m)
        {
            cin>>x>>y;
            v[x].PB(y);
            deg[y]++;
        }
        fr(i,n) if(deg[i]==0) v[0].PB(i);

        fr(i,n)
        {
            cur=i, v1.clear();
            fr(j,n) vis[j]=0;
            dfs(0);
            fr(j,n) if(vis[j]==0)
            {
                v1.PB(j);
                ans[i][j]=ans[j][i]=0;
            }
            for(auto it:v1) for(auto it2:v1)
                ans[it][it2]=0;
        }
        cnt=0;
        fr(i,n) for(j=i+1;j<=n;j++) cnt+=ans[i][j];
        cout<<cnt<<endl;
    }
    return 0;
}

Second solution

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 500 + 14;

int n, m, ban, in[maxn];
vector<int> g[maxn];
bool seen[maxn], ok[maxn][maxn];
void dfs(int v){
    if(seen[v] || v == ban)
        return;
    seen[v] = 1;
    for(auto u : g[v])
        dfs(u);
}
void solve(){
    cin >> n >> m;
    fill(g, g + n, vector<int> ());
    fill(in, in + n, 0);
    for(int i = 0; i < m; i++){
        int v, u;
        cin >> v >> u;
        v--, u--;
        g[v].push_back(u);
        in[u]++;
    }
    memset(ok, 1, sizeof ok);
    for(ban = 0; ban < n; ban++){
        fill(seen, seen + n, 0);
        for(int i = 0; i < n; i++)
                if(!in[i])
                dfs(i);
        for(int i = 0; i < n; i++)
            for(int j = 0; j < n; j++)
                if(!seen[i] && !seen[j])
                    ok[i][j] = 0;
    }
    int ans = 0;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < i; j++)
            ans += ok[i][j];
    cout << ans << 'n';
}
int main(){
    ios::sync_with_stdio(0), cin.tie(0);
    int t;
    cin >> t;
    while(t--){
        solve();
    }
}

HackerEarth Separate paths problem solution

HackerEarth Separate paths problem solution.

Second solution

Leave a Reply

Pages

Practice