Group of friends

There is a group of n people indexed by positive integers from 1 to n forming a network of friendship.

Friendship of x and y is denoted by a pair(x,y), which means x and y are friends.

If x is friend of y and y is friend of z , z is friend of friend of x.

We'd like to find out maximal sum of friends of friends of people among the group.

Input Format

The first line is n .
The second line is m , which is number of friend-pairs in the network of friendship.
The following m lines are friend-pairs.

Sample Input 0

5
6
1 2
1 3
2 3
2 4
3 5
4 5
Sample Output 0

14

The code below is the answer, but I got a hard time understanding why is there a u--, v--; in line 8
and also, what is the meaning of line 16~22, is that what we should usually do to an adjacency list?

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, m; cin >> n >> m;
    // adjacency list
    vector<vector<int>> graph(n);
    for (int i = 0; i < m; i++) {
        int u, v; cin >> u >> v; u--, v--;
        graph[u].emplace_back(v);
        graph[v].emplace_back(u);
    }

    int ans = 0;
    for (int i = 0; i < n; i++) {
        vector<bool> vis(n, false);
        for (auto u : graph[i]) {
            for (auto v : graph[u]) {
                vis[v] = true;
            }
        }
        int sum = 0;
        vis[i] = false;
        for (int j = 0; j < n; j++) {
            if (vis[j]) sum += j+1;
        }
        ans = max(sum, ans);
    }
    cout << ans << endl;
}

Last edited on

seeplus (6591)

The pairs are used as index into vector. vector indexes start at 0 not 1. Hence u-- v-- to make them 0 based and not 1 based.

L16 -22. These are range-for loops. L16 u will take the value for each element in graph during the iteration of graph. similar for L17.

See https://en.cppreference.com/w/cpp/language/range-for

Pen72 (74)

How about vis[v] = true; and vis[i] = false;

Last edited on

Topic archived. No new replies allowed.