ToB企服应用市场:ToB评测及商务社交产业平台

标题: 【华为OD机试B卷】服务器广播、需要广播的服务器数量（C++/Java/Python） [打印本页]
作者: 王海鱼    时间: 2024-7-10 19:59
标题: 【华为OD机试B卷】服务器广播、需要广播的服务器数量（C++/Java/Python）
标题

   [size=3
]标题形貌

  服务器连接方式包罗直接相连，间接连接。
  A和B直接连接，B和C直接连接，则A和C间接连接。
  直接连接和间接连接都可以发送广播。
  给出一个N*N数组，代表N个服务器，
  matrix[j] &#61
;&#61
; 1
，
则代表i和j直接连接&#xff1
b;不等于 1
时，代表i和j不直接连接。
  matrix &#61
;&#61
; 1
，
  即自己和自己直接连接。matrix[j] &#61
;&#61
; matrix[j]。
  计算初始需要给几台服务器广播， 才可以使每个服务器都收到广播。
  [size=3
]输入

  输入为N行，每行有N个数字，为0或1
，由空格分隔，
  构成N*N的数组，N的范围为 1
<&#61
; N <&#61
; 40
  [size=3
]输出

  输出一个数字，为需要广播的服务器的数量
  [size=1
]

  [size=3
]用例一

  输入
  1. 1
  2. 0 0
  3. 0 1
  4. 0
  5. 0 0 1
复制代码
输出
  1. 3
复制代码
说明
  3
台服务器互不连接，所以需要分别广播这 3
台服务器
  
  [size=3
]用例二

  输入
  1. 1
  2. 1
  4. 1
  5. 1
复制代码
输出
  1. 1
复制代码
说明
  2 台服务器相互连接，所以只需要广播其中一台服务器
  实当代码

C&#43
;&#43
;

  1. #include <iostream>#include <vector>using namespace std;int count &#61
  2. ; 0;void dfs(vector<vector<int>>& arr, vector<bool>& visited, int index) {    visited[index] &#61
  3. ; true;    bool flag &#61
  4. ; true;    for (int i &#61
  5. ; index &#43
  6. ; 1
  7. ; i < arr.size(); i&#43
  8. ;&#43
  9. ;) {        if (arr[index][i] &#61
  10. ;&#61
  11. ; 1
  12. ) {            flag &#61
  13. ; false;            dfs(arr, visited, i);        }    }    if (flag) {        count&#43
  14. ;&#43
  15. ;;    }}int main() {    string input;    getline(cin, input);    vector<string> str;    size_t pos &#61
  16. ; 0;    while ((pos &#61
  17. ; input.find(&#3
  18. 4; &#3
  19. 4;)) !&#61
  20. ; string::npos) {        str.push_back(input.substr(0, pos));        input.erase(0, pos &#43
  21. ; 1
  22. );    }    str.push_back(input);    int n &#61
  23. ; str.size();    vector<vector<int>> arr(n, vector<int>(n, 0));    for (int i &#61
  24. ; 0; i < n; i&#43
  25. ;&#43
  26. ;) {        arr[0][i] &#61
  27. ; stoi(str[i]);    }    for (int i &#61
  28. ; 1
  29. ; i < n; i&#43
  30. ;&#43
  31. ;) {        getline(cin, input);        pos &#61
  32. ; 0;        vector<string> s;        while ((pos &#61
  33. ; input.find(&#3
  34. 4; &#3
  35. 4;)) !&#61
  36. ; string::npos) {            s.push_back(input.substr(0, pos));            input.erase(0, pos &#43
  37. ; 1
  38. );        }        s.push_back(input);        for (int j &#61
  39. ; 0; j < n; j&#43
  40. ;&#43
  41. ;) {            arr[i][j] &#61
  42. ; stoi(s[j]);        }    }    vector<bool> visited(n, false);    for (int i &#61
  43. ; 0; i < n; i&#43
  44. ;&#43
  45. ;) {        if (!visited[i]) {            dfs(arr, visited, i);        }    }    cout << count << endl;    return 0;}
复制代码
Java

  1. import java.util.*;public class Main {    public static void main(String[] args) {        Scanner in &#61
  2. ; new Scanner(System.in);        String[] str &#61
  3. ; in.nextLine().split(&#3
  4. 4; &#3
  5. 4;);        int n &#61
  6. ; str.length;        int[][] arr &#61
  7. ; new int[n][n];        for(int i &#61
  8. ; 0; i < n; i&#43
  9. ;&#43
  10. ;) {               arr[0][i] &#61
  11. ; Integer.parseInt(str[i]);        }        for(int i &#61
  12. ; 1
  13. ; i < n; i&#43
  14. ;&#43
  15. ;) {               String[] s &#61
  16. ; in.nextLine().split(&#3
  17. 4; &#3
  18. 4;);            for(int j &#61
  19. ; 0; j < n; j&#43
  20. ;&#43
  21. ;) {                arr[i][j] &#61
  22. ; Integer.parseInt(s[j]);            }        }        int count &#61
  23. ; 0;        Queue<Integer> queue &#61
  24. ; new LinkedList<>();        for(int i &#61
  25. ; 0; i < n; i&#43
  26. ;&#43
  27. ;) {            if(!queue.contains(i)) {                dfs(arr, queue, i);                count&#43
  28. ;&#43
  29. ;;            }        }        System.out.println(count);    }        public static void dfs(int[][] arr, Queue<Integer> queue, int index) {        queue.offer(index);        for (int i &#61
  30. ; index &#43
  31. ; 1
  32. ; i < arr.length; i&#43
  33. ;&#43
  34. ;) {            if (arr[index][i] &#61
  35. ;&#61
  36. ; 1
  37. && !queue.contains(i)) {                dfs(arr, queue, i);            }        }    }}
复制代码
Python

  1. import sysdef dfs(arr, visited, index):    visited[index] &#61
  2. ; True    flag &#61
  3. ; True    for i in range(index &#43
  4. ; 1
  5. , len(arr)):        if arr[index][i] &#61
  6. ;&#61
  7. ; 1
  8. :            flag &#61
  9. ; False            dfs(arr, visited, i)    if flag:        global count        count &#43
  10. ;&#61
  11. ; 1
  12. count &#61
  13. ; 0str &#61
  14. ; input().split(&#3
  15. 4; &#3
  16. 4;)n &#61
  17. ; len(str)arr &#61
  18. ; [[0]*n for _ in range(n)]for i in range(n):    arr[0][i] &#61
  19. ; int(str[i])for i in range(1
  20. , n):    s &#61
  21. ; input().split(&#3
  22. 4; &#3
  23. 4;)    for j in range(n):        arr[i][j] &#61
  24. ; int(s[j])visited &#61
  25. ; [False]*nfor i in range(n):    if not visited[i]:        dfs(arr, visited, i)print(count)
复制代码
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao1
23
.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。



欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/) Powered by Discuz! X3.4