P2097 资料分发1

admin

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

用简单的图的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. */
    

复制代码