一本通 3.4.3 图的连通性

1383：刻录光盘(cdrom)

【题目描述】

在FJOI2010夏令营快要结束的时候，很多营员提出来要把整个夏令营期间的资料刻录成一张光盘给大家，以便大家回去后继续学习。组委会觉得这个主意不错！可是组委会一时没有足够的空光盘，没法保证每个人都能拿到刻录上资料的光盘，怎么办呢？！

DYJ分析了一下所有营员的地域关系，发现有些营员是一个城市的，其实他们只需要一张就可以了，因为一个人拿到光盘后，其他人可以带着U盘之类的东西去拷贝啊！

他们愿意某一些人到他那儿拷贝资料，当然也可能不愿意让另外一些人到他那儿拷贝资料，这与我们FJOI宣扬的团队合作精神格格不入！！！

现在假设总共有N个营员（2<=N<=200），每个营员的编号为1~N。DYJ给每个人发了一张调查表，让每个营员填上自己愿意让哪些人到他那儿拷贝资料。当然，如果A愿意把资料拷贝给B，而B又愿意把资料拷贝给C，则一旦A获得了资料，则B，C都会获得资料。

现在，请你编写一个程序，根据回收上来的调查表，帮助DYJ计算出组委会至少要刻录多少张光盘，才能保证所有营员回去后都能得到夏令营资料？

【题目分析】

本题三种代码实现都是在问题转化理解1的基础之上。

问题转化理解2的实现代码参考SSL 2344 洛谷 2835 信息学奥赛一本通 1383 刻录光盘#floyd,tarjan,kosaraju#_lemondinosaur的博客-CSDN博客

【代码实现】

方法1：

#include<iostream>
#include<cstring>
using namespace std;
int n, m, b, s, a[205], c[205], d[205][205];
void dfs1(int o) { //深搜c[o] = 1; //标记for (int i = 1; i <= n; i++) //有相连就搜下去if (d[o][i] == 1 && c[i] == 0)dfs1(i);m++;a[m] = o; //将退出顺序存好}
void dfs2(int o) { //深搜c[o] = 1; //标记for (int i = 1; i <= n; i++) //搜下去if (d[o][i] == 1 && c[i] == 0)dfs2(i);
}
int main() {cin >> n;for (int i = 1; i <= n; i++) {cin >> b;while (b != 0) {d[i][b] = 1; //邻接矩阵cin >> b;}}for (int i = 1; i <= n; i++) //先搜一遍，以1为起点if (c[i] == 0)dfs1(i);memset(c, 0, sizeof(c)); //清零for (int i = m; i >= 1; i--) //退出顺序搜下去if (c[a[i]] == 0) {s++;  //加加dfs2(a[i]);}cout << s;
}

方法2：

#include <bits/stdc++.h>using namespace std;int n, mp[205][205];
int rec[205];int main() {//input datacin >> n;for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {if (i == j) mp[i][i] = 1;elsemp[i][j] = 0;}}for (int i = 1; i <= n; i++) {int a;while (cin >> a, a != 0) mp[i][a] = 1;rec[i] = i;}for (int k = 1; k <= n; k++) {for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {mp[i][j] |= (mp[i][k] & mp[k][j]);}}}for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {if (mp[i][j]) rec[j] = rec[i];}}int cnt = 0;for (int i = 1; i <= n; i++) {if (rec[i] == i) cnt++;}cout << cnt;return 0;
}

方法3：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 500;
/*1、可能具有独立环2、有向图 搜索起点会影响搜索结果
*/
int n, m;
struct Edge {int next;int to;
} edge[maxn * 40];
int head[maxn], _count = 0;void add_edge(int from, int to) {edge[++_count].next = head[from];head[from] = _count;edge[_count].to = to;
}
int mark[maxn];bool dfs(int u, int fafa) {bool flag = 0;int k = head[u];while (k != 0) {int v = edge[k].to;if (mark[v] == 0) {mark[v] = 1;flag = flag || dfs(v, fafa);} else if (mark[v] == 2) {if (v != fafa) {mark[v] = 1;flag = 1;}}k = edge[k].next;}return flag;
}
int main() {//input data//clock_t s = clock();cin >> n;for (int i = 1; i <= n; i++) {int x;cin >> x;while (x != 0) {add_edge(i, x);cin >> x;}}//dfsint ans = 0;for (int i = 1; i <= n; i++) {if (mark[i] == 0) {mark[i] = 2;if (!dfs(i, i))ans++;}}cout << ans;//output time//cout <<endl<< clock() - s<<endl;return 0;
}

1384：珍珠(bead)

【题目描述】

有n颗形状和大小都一致的珍珠，它们的重量都不相同。n为整数，所有的珍珠从1到n编号。你的任务是发现哪颗珍珠的重量刚好处于正中间，即在所有珍珠的重量中，该珍珠的重量列(n+1)/2位。下面给出将一对珍珠进行比较的办法：

给你一架天平用来比较珍珠的重量，我们可以比出两个珍珠哪个更重一些，在作出一系列的比较后，我们可以将某些肯定不具备中间重量的珍珠拿走。

例如，下列给出对5颗珍珠进行四次比较的情况：

1、珍珠2比珍珠1重

2、珍珠4比珍珠3重

3、珍珠5比珍珠1重

4、珍珠4比珍珠2重

根据以上结果，虽然我们不能精确地找出哪个珍珠具有中间重量，但我们可以肯定珍珠1和珍珠4不可能具有中间重量，因为珍珠2、4、5比珍珠1重，而珍珠1、2、3比珍珠4轻，所以我们可以移走这两颗珍珠。

写一个程序统计出共有多少颗珍珠肯定不会是中间重量。

【题目分析】

【代码实现】

#include <bits/stdc++.h>
using namespace std;
const int maxn = 100;
int n, m;
int e[maxn][maxn];int main() {//input data//clock_t s = clock();cin >> n >> m;for (int i = 1; i <= m; i++) {int x, y;cin >> x >> y;e[x][y] = 1;}//floyedfor (int k = 1; k <= n; k++)for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)e[i][j] = e[i][j] || (e[i][k] && e[k][j]);int mid = (n + 1) / 2;int ans_max[maxn];int ans_min[maxn];memset(ans_max, 0, sizeof(ans_max));memset(ans_min, 0, sizeof(ans_min));for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {if (e[i][j]) {ans_max[i]++;ans_min[j]++;}}}int sum = 0;for (int i = 1; i <= n; i++) {if (ans_max[i] >= mid || ans_min[i] >= mid) sum++;}cout << sum;//output time//cout <<endl<< clock() - s<<endl;return 0;
}