DFS搜索入门（第一次写不完善的还请指出，谢谢大家支持）

题意：给定从1到n的n个数，这些数中有一些和其他数存在一种关系。给定所有关系，并给初值ans为1；将这n个数以一种顺序取出，（每当取出的数与之前已取出的数存在关系，ans值将翻倍。）最后使得ans值最大。

思路解析：本题中数字间关系可以在图中表示出来。列如n = 9；m = 9；（1,2）； （1,4）； （2,3）； （2,4）； （7,2）；（4,7）；（5,8）；（5,6）；（8,6）； 这样就可以将数字间的关系用图清晰的表示出来，而任意一个连通图中的点的个数p决定ans值最大的翻倍次数为p - 1次，这点我们由连通图通过去边来使它生成一颗生成树；如图：

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;

const int MaxN = 100;
int n, m, a, b, p;
long long ans;
bool c[MaxN + 5][MaxN + 5], loc[MaxN + 5]; //c[x][y] == 1表示x与y之间存在关系。

void Dfs(int x)
{
　　for(int i = 1; i <= n; i++)
　　{
　　　　if(c[x][i] == 1 && loc[i] == 0) {loc[i] = 1; p++; Dfs(i);}
　　}
}

int main()
{
　　scanf("%I64d %I64d", &n, &m);
　　memset(c, 0, sizeof(c));
　　memset(loc, 0, sizeof(loc));
　　for(int i = 1; i <= m; i++)　　　　//读入所有数字间的关系。
　　{
　　　　scanf("%d %d", &a, &b);
　　　　c[a][b] = 1;
　　　　c[b][a] = 1;
　　}
　　ans = 1;
　　for(int i = 1; i <= n; i++)
　　{
　　　　p = 0;　　　　　　//p值记录每一个连通图所拥有的点的个数。
　　　　if(!loc[i]) 　　　　//loc[i] = 1表示此点已被搜索过
　　　　{
　　　　　　loc[i] = 1;
　　　　　　p++;
　　　　　　Dfs(i);
　　　　}
　　　　for(int j = 1; j <= p - 1; j++) ans *= 2;
　　}
　　printf("%I64d\n", ans);
}

本题难点在于合理的将所有的数搜索过，且明白每个连通图都可以得出最优答案，通过作图和由图生成的树来得到答案，使杂乱的数字关系直观表示出来。

DFS搜索入门（第一次写不完善的还请指出，谢谢大家支持）

原文：http://www.cnblogs.com/chenjiaqi-acm/p/4992552.html