We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Journey to the Moon
Journey to the Moon
Sort by
recency
|
502 Discussions
|
Please Login in order to post a comment
Here’s a step-by-step approach to solve this problem in PHP:
Model the Problem as a Graph:
Find Connected Components:
Calculate the Number of Valid Pairs:
Here's the PHP 5.6 solution:
Explanation:
Graph Construction:
Finding Connected Components:
dfs
) is used to find the size of each connected component.Calculating Valid Pairs:
Usage:
include
using namespace std;
template class Graph { map> l;
public: void addEdge(T x, T y) { l[x].push_back(y); l[y].push_back(x); }
void dfs_helper(T src, map &visited, vector &component) { visited[src] = true; component.push_back(src); for (T nbr : l[src]) { if (!visited[nbr]) { dfs_helper(nbr, visited, component); } } }
map> dfs() { map> components; map visited;
}
long long factorial(int n) { if (n == 0 || n == 1) return 1; long long result = 1; for (int i = 2; i <= n; ++i) { result *= i; } return result; }
long long nCr(int n, int r) { if (r > n) return 0; // Return 0 if r is greater than n if (r == 0 || n == r) return 1; // nC0 or nCn is 1
}
};
int main() { Graph g;
int n, p; cin >> n >> p;
while (p--) { int n1, n2; cin >> n1 >> n2; g.addEdge(n1, n2); }
map> components = g.dfs();
long long res = g.nCr(n, 2); for (auto it = components.begin(); it != components.end(); ++it) { int component_size = it->second.size(); if (component_size >= 2) { res -= g.nCr(component_size, 2); } }
cout << res << endl;
return 0; }
NOTE: Case 11 fails because the result is too large to be supported by a 32-bit integer. You'll need to set the return type to a 64-bit integer to get it to work.
With that being said, here's a solution I've made in Java 8 that passes all test cases...
C++ (more at https://github.com/IhorVodko/Hackerrank_solutions , feel free to give a star)
Change function return type and 'cout' type to 'size_t' (given type 'int' overflows for the test case 11)
Ruby