华师一附中OI组

标题: P2097 资料分发1 [打印本页]
作者: admin    时间: 2021-3-30 09:33
标题: P2097 资料分发1
https://www.luogu.com.cn/problem/P2097

题目描述
有一些电脑，一部分电脑有双向数据线连接。如果一个电脑得到数据，它可以传送到的电脑都可以得到数据。现在，你有这个数据，问你至少将其输入几台电脑，才能使所有电脑得到数据。

输入格式
第一行两个数n，m。n是点数，m是边数。

接下来m行，每行2个整数p，q表示p到q有一条双向数据线。

输出格式
一个整数，表示至少输入的电脑数量。

输入输出样例
输入 #1复制
4 5
1 2
1 3
2 3
2 1
3 4
输出 #1复制
1
说明/提示
对于30%的数据：n<=100,m<=1000

对于60%的数据:n<=2000,m<=100000

对于100%的数据：n<=100000, m<=200000

数据不保证没有重边，不保证没有自回环
作者: admin    时间: 2021-3-30 09:44
用简单的图的DFS方法，类似种子填充算法来做是可行的。
考察读入建图的基本功和基本的DFS方法。
  1. ///  2097种子填充算法
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. const int mn=100010;
  5. const int mm=400010; //  双向边注意开2倍
  6. int n,m,cnt;
  7. int nbs[mn],vis[mn];
  8. int ev[mm],nxt[mm];  //  eu和ew都无必要
  9. void readmap()
  10. {
  11.         int u,v;
  12.         cin>>n>>m;
  13.         for (int i=1; i<=n; i++) nbs[i]=vis[i]=0;
  14.         for (int i=1; i<=m; i++)
  15.                 {
  16.                         cin>>u>>v;//双向边
  17.                         ev[i]=v,nxt[i]=nbs[u],nbs[u]=i;
  18.                         ev[i+m]=u,nxt[i+m]=nbs[v],nbs[v]=i+m;
  19.                 }
  20. }
  21. void showmap()  //检查建图情况
  22. {
  23.         for (int i=1; i<=n; i++)
  24.                 {
  25.                         cout<<i<<':';
  26.                         for (int j=nbs[i]; j; j=nxt[j]) cout<<setw(3)<<ev[j]<<' ';
  27.                         cout<<endl;
  28.                 }
  29. }
  30. void dfs(int p)
  31. {
  32.         vis[p]=cnt;
  33.         for (int i=nbs[p]; i!=0; i=nxt[i])
  34.                 {
  35.                         int v=ev[i]; //常规无聊直观操作
  36.                         if (vis[v]==0)dfs(v);
  37.                 }
  38. }
  39. void pp()
  40. {
  41.         for(int i=1; i<=n; i++) cout<<setw(3)<<vis[i];
  42.         cout<<endl;
  43. }
  44. int main()
  45. {
  46.         readmap();
  47.         //showmap();
  48.         cnt=0;
  49.         for(int i=1; i<=n; i++)
  50.                 {
  51.                         if (vis[i]==0)
  52.                                 {
  53.                                         ++cnt;
  54.                                         dfs(i);
  55.                                 }
  56.                 }
  57.         cout<<cnt;
  58.         return 0;
  59. }
  60. /*
  61. 4 5
  62. 1 2
  63. 1 3
  64. 2 3
  65. 2 1
  66. 3 4
  67. */
复制代码




欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2