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.
int cnt = 0;
for (auto p : l)
{
T node = p.first;
visited[node] = false;
}
for (auto p : l)
{
T node = p.first;
if (!visited[node])
{
vector<T> component;
dfs_helper(node, visited, component);
components[cnt++] = component;
}
}
return components;
}
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
r = min(r, n - r); // Optimize to reduce computations
long long result = 1;
for (int i = 1; i <= r; ++i) {
result *= n - i + 1;
result /= i;
}
return result;
}
};
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;
}
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Journey to the Moon
You are viewing a single comment's thread. Return to all comments →
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; }