当前位置：网站首页>【小码匠自习室】朋友的朋友不是朋友

【小码匠自习室】朋友的朋友不是朋友

2022-08-08 13:53:00 【小码匠】

标签

  • 图、无向图

题目地址

Q4. 友達の友達

  • https://algo-method.com/tasks/413

問題描述

输入

输出

输出结果

输入示例 1

6 7 0
0 1
0 5
1 3
1 5
2 3
3 4
4 5

输入示例 1

2

六种朋友的关系如下面的图。

阿尔勒的朋友是学生 1 和学生 5，阿尔勒的朋友的朋友是学生 3 和学生 4。由于 阿尔勒 有两个“朋友的朋友”，我们将输出 2。

输入示例 2

5 7 2
0 2
0 3
1 2
1 4
2 3
2 4
3 4

输出示例 2

0

阿尔勒和学校所有学生都是朋友，所以朋友的朋友为：0

题解

小码匠题解

#include <bits/stdc++.h>
using namespace std;
#define endl '\n';
void coder_solution();

int main() {
    // 小码匠
    coder_solution();

    // 返回
    return 0;
}

void coder_solution() {
    // 提升cin、cout效率
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    // 提升cin、cout效率
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m, x, a, b;
    cin >> n >> m >> x;
    vector<vector<int>> c(n);
    for(int i = 0; i < m; ++i) {
        cin >> a >> b;
        c[a].push_back(b);
        c[b].push_back(a);
    }
    unordered_set<int> ans;
    set<int> f;
    for(auto i : c[x]) {
        f.insert(i);
    }
    for(auto i : c[x]) {
        for (auto j : c[i]) {
            if (!f.count(j) && j != x) {
                ans.insert(j);
            }
        }
    }

    cout << ans.size();
}
原网站

版权声明
本文为[小码匠]所创，转载请带上原文链接，感谢
https://cloud.tencent.com/developer/article/2068167

边栏推荐

猜你喜欢

随机推荐