## Intuition The problem asks us to verify if a given social network satisfies a specific condition: for any three members X, Y, and Z, if X is friends with Y and Y is friends with Z, then X must also be friends with Z. This condition essentially means that each connected component of the graph should be a complete graph (clique). If any connected component is not a complete graph, the network is not reasonable. ## Approach 1. **Graph Representation**: Represent the social network as an undirected graph where nodes are members and edges are friendships. 2. **Connected Components**: Use Depth First Search (DFS) or Union-Find to find all connected components in the graph. 3. **Check Each Component**: For each connected component, check if it forms a complete graph. A component with `k` nodes should have exactly `k * (k - 1) / 2` edges to be a complete graph. 4. **Verification**: If all components are complete graphs, print "YES". Otherwise, print "NO". ## Complexity - **Time Complexity**: O(n + m), where `n` is the number of members and `m` is the number of friendships. This is due to the graph traversal and edge counting. - **Space Complexity**: O(n + m) for storing the graph and visited nodes. ## Solution (C++) ```cpp #include using namespace std; void dfs(int node, vector>& adj, vector& visited, vector& component) { stack s; s.push(node); visited[node] = true; while (!s.empty()) { int u = s.top(); s.pop(); component.push_back(u); for (int v : adj[u]) { if (!visited[v]) { visited[v] = true; s.push(v); } } } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; vector> adj(n + 1); for (int i = 0; i < m; ++i) { int a, b; cin >> a >> b; adj[a].push_back(b); adj[b].push_back(a); } vector visited(n + 1, false); for (int i = 1; i <= n; ++i) { if (!visited[i]) { vector component; dfs(i, adj, visited, component); long long numNodes = component.size(); long long numEdges = 0; for (int node : component) { numEdges += adj[node].size(); } numEdges /= 2; // Each edge is counted twice if (numEdges != numNodes * (numNodes - 1) / 2) { cout << "NO\n"; return 0; } } } cout << "YES\n"; return 0; } ``` This solution uses DFS to explore each connected component and checks if the component is a complete graph by comparing the number of edges to the expected number for a complete graph. If any component fails this check, the network is not reasonable.

Bear and Friendship Condition

Problem Details