【易】并查集 25分

发布时间:2019年03月16日 阅读:296 次

7-12 文件传输 (25 分)

当两台计算机双向连通的时候,文件是可以在两台机器间传输的。给定一套计算机网络,请你判断任意两台指定的计算机之间能否传输文件?

输入格式:

首先在第一行给出网络中计算机的总数 (),于是我们假设这些计算机从 1 到 编号。随后每行输入按以下格式给出:

  1. I c1 c2

其中I表示在计算机c1c2之间加入连线,使它们连通;或者是

  1. C c1 c2

其中C表示查询计算机c1c2之间能否传输文件;又或者是

  1. S

这里S表示输入终止。

输出格式:

对每个C开头的查询,如果c1c2之间可以传输文件,就在一行中输出"yes",否则输出"no"。当读到终止符时,在一行中输出"The network is connected."如果网络中所有计算机之间都能传输文件;或者输出"There are k components.",其中k是网络中连通集的个数。

输入样例 1:

  1. 5
  2. 3 2
  3. 3 2
  4. 1 5
  5. 4 5
  6. 2 4
  7. 3 5
  8. S

输出样例 1:

  1. no
  2. no
  3. yes
  4. There are 2 components.

输入样例 2:

  1. 5
  2. 3 2
  3. 3 2
  4. 1 5
  5. 4 5
  6. 2 4
  7. 3 5
  8. 1 3
  9. 1 5
  10. S

输出样例 2:

  1. no
  2. no
  3. yes
  4. yes
  5. The network is connected.
C++
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int f[12000];
  4. int getf(int x)
  5. {
  6. if(x==f[x])return x;
  7. else
  8. {
  9. f[x] = getf(f[x]);
  10. return f[x];
  11. }
  12. }
  13. void Merge(int a,int b)
  14. {
  15. int aa = getf(a);
  16. int bb = getf(b);
  17. if(aa!=bb)
  18. {
  19. f[aa] = bb;
  20. }
  21. }
  22. int aa,bb;
  23. int main()
  24. {
  25. int n;
  26. cin>>n;
  27. for(int i=1;i<=n;i++)
  28. f[i] =i;
  29. string tt;
  30. while(cin>>tt)
  31. {
  32. if(tt[0]=='S')
  33. {
  34. int sum =0;
  35. for(int i=1;i<=n;i++)
  36. {
  37. if(f[i]==i)sum++;
  38. }
  39. if(sum==1)
  40. printf("The network is connected.\n");
  41. else
  42. printf("There are %d components.\n",sum);
  43. break;
  44. }
  45. else if(tt[0]=='C')
  46. {
  47. cin>>aa>>bb;
  48. if(getf(aa)==getf(bb))
  49. {
  50. printf("yes\n");
  51. }
  52. else printf("no\n");
  53. }
  54. else
  55. {
  56. cin>>aa>>bb;
  57. Merge(aa,bb);
  58. }
  59. }
  60. return 0;
  61. }


Tag:
相关文章
发表评论

发表评论: