dfs算法第二次加训之普及/提高- ，详解 上
dfs这种递归的题一直是我的弱项，有时候经常因为一道题卡我一天，（我太笨蛋了哈），我老是脑子想不通咋return的，咋就把值传过去了，还有有时候for循环嵌套dfs，有时候一路两搜索，有时候遍历图用visited，有时候是子节点!=父节点等等吧，但是我发现只要做得多，然后后就是仔细去思考或者说把这些结构比喻成某种事物，就会理解，希望我写的一些思路和代码能让不会的人有些思路吧（其实大部分原因还是怕自己写过得体给忘了，把自己的答案和思路扔在这里让自己以后还能复个习，我太笨了）
目录
P1037 [NOIP 2002 普及组] 产生数
思路
P1123 取数游戏
思路
P1135 奇怪的电梯
思路
P1219 [USACO1.5] 八皇后 Checker Challenge
思路
P1330 封锁阳光大学
思路
P1118 [USACO06FEB] Backward Digit Sums G/S
思路
P2052 [NOI2011] 道路修建
思路
P2196 [NOIP 1996 提高组] 挖地雷
思路：
P2420 让我们异或吧
思路 ：
P2853 [USACO06DEC] Cow Picnic S
思路
B3624 猫粮规划
思路
P3848 [TJOI2007] 跳棋
思路
P3864 [USACO1.2] 命名那个数字 Name That Number
思路
P3884 [JLOI2009] 二叉树问题
思路
P3915 树的分解
思路
B4016 树的直径
思路
P4017 最大食物链计数
思路：
P1037 [NOIP 2002 普及组] 产生数
题目描述
给出一个整数 n 和 k 个变换规则。
规则：
- 一位数可变换成另一个一位数。
- 规则的右部不能为零。
例如：n=234,k=2。有以下两个规则：
- 2⟶5。
- 3⟶6。
上面的整数 234 经过变换后可能产生出的整数为（包括原数）:
- 234。
- 534。
- 264。
- 564。
共 4 种不同的产生数。
现在给出一个整数 n 和 k 个规则。求出经过任意次的变换（0 次或多次），能产生出多少个不同整数。
仅要求输出个数。
输入格式
第一行两个整数 n,k，含义如题面所示。
接下来 k 行，每行两个整数 xi,yi，表示每条规则。
输出格式
共一行，输出能生成的数字个数。
输入输出样例
输入 #1复制
234 2 2 5 3 6输出 #1复制
4说明/提示
对于 100% 数据，满足 n<10^30，k≤15。
思路
要组合数嘛，先举个例子1现在给你1 2 3，这三个数让你组成不同的三位数 那是不是就是3*3*3个不同的组合，那同样的，这道题，看样例，他给你2->5,3->6,那就是相当于4放那不动
求？？4，这个样例，第一个问号可以是2或5,第二个？可以是3或6，那我们得到的所有组合是不是就是2*2。。。我再多说一下，如果再给个5->1那第一个？就是3个数在变化了，所以我们可以建图，以此来看一个数能变多少个就好，又因为题目给的数据很大说明肯定是高精度，好了这就是所有重点了 看代码
#include<bits/stdc++.h>
using namespace std;
int ans, n;
vector<int>graph[15]; // 邻接表
int res[35];
bool vis[10];
void dfs(int x) { if(vis[x])return;//这个变过了就不变了 vis[x]=true; ans++; for (auto v:graph[x]) { dfs(v); }
} void multi(int x) {
//从1开始到30,1就是最低位
//模拟乘法,jw就是乘之后需要进的位，初始为0 int jw=0; //进位的数 for (int i=1;i<=30;i++) { res[i]=res[i]*x+jw; jw=res[i]/10; //需要进的位 res[i]%=10;//乘之后余数就是这个位的值 }
}
int main() { string s; cin>>s>>n; for (int i=1;i<=n;i++) { int x,y; cin>>x>>y; graph[x].push_back(y); // 添加边 } res[1]=1; // 数组初始化为1 for (int i = 0; i <(int)s.size(); i++) {//把每位的数都搜索，不能转变的话在搜索里面就直接停了，所以不用在意这些//用ans记录每个数能变几次 ans=0; memset(vis,0,sizeof(vis));dfs(s[i]-'0'); multi(ans); } int pos=30; while (res[pos]==0&&pos>1)pos--; // 删除前导0for (int i=pos;i>0;i--)cout<<res[i]; // 输出 return 0;
} P1123 取数游戏
题目描述
一个 N×M 的由非负整数构成的数字矩阵，你需要在其中取出若干个数字，使得取出的任意两个数字不相邻（若一个数字在另外一个数字相邻 8 个格子中的一个即认为这两个数字相邻），求取出数字和最大是多少。
输入格式
第一行有一个正整数 T，表示了有 T 组数据。
对于每一组数据，第一行有两个正整数 N 和 M，表示了数字矩阵为 N 行 M 列。
接下来 N 行，每行 M 个非负整数，描述了这个数字矩阵。
输出格式
共 T 行，每行一个非负整数，输出所求得的答案。
输入输出样例
输入 #1复制
3 4 4 67 75 63 10 29 29 92 14 21 68 71 56 8 67 91 25 2 3 87 70 85 10 3 17 3 3 1 1 1 1 99 1 1 1 1输出 #1复制
271
172
99
思路
可能是最近一直在写这种递归回溯搜索混一起的题，看见这个脑子陷进去了，脑子一直在递归，就是一直在想选或不选，这些操作后咋办咋办，正好通过这题再把脑子对dfs的理解更深一些
dfs深搜嘛，核心就是递归，一直走到头，把所有能走的都走一遍找到你要的结果，比如1 2 3 4 5 6
这6个代表6个东西，我们要选3个符合我们要求的东西，我们就去搜索，我们从第一个开始搜，对于第一个我们有选或不选的能力，选第一个和不选第一个之后出来的结果当然不一样，有些题会带上第一个的重量，那我们就弄个sum，然后我们选择选第一个那sum就加上weight[1]第一个重量，然后现在就假设选第一个的路都走完了，然后回到当前的程序里，我们还有个情况就是不选第一个，那我们就要减去之前加的这个重量就好，其实我现在把这些说出来还是很简单但是，也不知道为啥做这题时候脑子就是陷进去了
接下来才是这题真正的思路，上面是我刚刚脑子里的想法，这题让我们去找这个矩阵里面的几个数相加的最大值，但是我们选择的数，在此之前这个数的周围不能被选过，那我们就从第一个元素开始搜，一行一行搜，还是刚刚说的，遇到一个数就是两个情况，选或不选，刚刚也说了，只有周围曾经没被选过才可以被选，那我们就是分为，不选，和当这个数能选的时候选，是吧，我们用一个mark数组来标记一个数周围是否被选过，好我们来看代码，这个代码是我看题解写的，因为脑子当时陷进去了，脑子看的晕，看了题解其实也是懵，但是趴在桌子上休息一会然后又想了一会就想通了，
对于一路两搜索，当你选的时候是把选了后的状态带到下一层，当走这条路走完，我们就需要把这个状态回退，也就是我们所说的回溯，然后再走另一条路
#include<bits/stdc++.h>
using namespace std;
int mv[8][2]={1,0,-1,0,0,1,0,-1,1,1,-1,1,1,-1,-1,-1};;
int t,n,m,grid[10][10],mark[10][10],ans,ms;
//咱们是一行一行遍历搜索的
void dfs(int x,int y){//所以当走道的行数超过边界就搜下一行 if(y>m){dfs(x+1,1);return ;}if(x>n){ms=max(ms,ans);return;} //如果能取这个数，现在就是取这个数情况 if(mark[x][y]==0){//如果这个数周围没取过ans+=grid[x][y];for(int nx=0;nx<8;nx++){++mark[x+mv[nx][0]][y+mv[nx][1]];} dfs(x,y+1);//回溯for(int nx=0;nx<8;nx++){--mark[x+mv[nx][0]][y+mv[nx][1]];} ans-=grid[x][y];}dfs(x,y+1);//不取这个数情况
}
int main(){cin>>t;while(t--){memset(mark,0,sizeof(mark));cin>>n>>m;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>grid[i][j];}}ms=0;dfs(1,1);cout<<ms<<endl;}
} P1135 奇怪的电梯
题目描述
呵呵，有一天我做了一个梦，梦见了一种很奇怪的电梯。大楼的每一层楼都可以停电梯，而且第 i 层楼（1≤i≤N）上有一个数字 Ki（0≤Ki≤N）。电梯只有四个按钮：开，关，上，下。上下的层数等于当前楼层上的那个数字。当然，如果不能满足要求，相应的按钮就会失灵。例如： 3,3,1,2,5 代表了 Ki（K1=3，K2=3，……），从 1 楼开始。在 1 楼，按“上”可以到 4 楼，按“下”是不起作用的，因为没有 −2 楼。那么，从 A 楼到 B 楼至少要按几次按钮呢？
输入格式
共二行。
第一行为三个用空格隔开的正整数，表示 N,A,B（1≤N≤200，1≤A,B≤N）。
第二行为 N 个用空格隔开的非负整数，表示 Ki。
输出格式
一行，即最少按键次数，若无法到达，则输出
-1。输入输出样例
输入 #1复制
5 1 5 3 3 1 2 5输出 #1复制
3说明/提示
对于 100% 的数据，1≤N≤200，1≤A,B≤N，0≤Ki≤N。
本题共 16 个测试点，前 15 个每个测试点 6 分，最后一个测试点 10 分。
思路
题上已经给了两个选择，我们要向上或向下，但题目是有坑的，比如1楼贴的3,4楼贴的3，我们就可能进入循环中然后超时，所以我们要用一个min_step数组记录到达每一个地方时候这个地方走的最小操作数是多少，如果再走到这个地方的操作数比之前大那就直接return这样就行了，，接下来就看代码吧
#include<bits/stdc++.h>
using namespace std;
int n,a,b,k[210],ans=-1;
int min_step[210];
void dfs(int a,int cnt){//没有这行代码就要MLE了 if(cnt>=min_step[a]) return;//现在所走的操作数已经大于等于以前走过这个节点时候的操作数那就别走了//记录一下当前走这个节点时候的操作数 min_step[a]=cnt;//走到终点后记录一下最小操作数ans的值ans=cnt if(a==b) {ans=cnt;return;}//选上还是选下// 1. 选上，但要看看能不能选上，if(a+k[a]<=n){dfs(a+k[a],cnt+1);} // 2. 选下，同样看看，能不能选下if(a-k[a]>=1){dfs(a-k[a],cnt+1);}
}
int main(){cin>>n>>a>>b;for(int i=1;i<=n;i++){cin>>k[i];min_step[i]=1e9;}dfs(a,0);
cout<<(ans!=-1?ans:-1);
}P1219 [USACO1.5] 八皇后 Checker Challenge
题目描述
一个如下的 6×6 的跳棋棋盘，有六个棋子被放置在棋盘上，使得每行、每列有且只有一个，每条对角线（包括两条主对角线的所有平行线）上至多有一个棋子。
上面的布局可以用序列 2 4 6 1 3 5 来描述，第 i 个数字表示在第 i 行的相应位置有一个棋子，如下：
行号 1 2 3 4 5 6
列号 2 4 6 1 3 5
这只是棋子放置的一个解。请编一个程序找出所有棋子放置的解。
并把它们以上面的序列方法输出，解按字典顺序排列。
请输出前 3 个解。最后一行是解的总个数。
输入格式
一行一个正整数 n，表示棋盘是 n×n 大小的。
输出格式
前三行为前三个解，每个解的两个数字之间用一个空格隔开。第四行只有一个数字，表示解的总数。
输入输出样例
输入 #1复制
6
输出 #1复制
2 4 6 1 3 5 3 6 2 5 1 4 4 1 5 2 6 3 4
思路
我们以行作为递归深度，从第0行开始，当第一行找到一个合适的位置（我们用check检查），然后用path数组存储这个列（为什么存储列呢，因为题目要求我们输出每个皇后所在列数），怎么存储呢，path[row]=col，也就是ans的第row个数等于当前for到的遍历到的列数，row是递归到的层数，，当row到达n层也就是递归的深度最大时候，就把path存到的皇后位置给res，
我们的ans在check函数里的应用也是非常妙，大体就是这样，代码写的很漂亮，看完应该就懂了
我再多说一点，可能有人不懂我的这个回溯的这个代码，我们用for循环来遍历这一行的每一列，然后看每一层递归这一行的某一列是否能放棋子（通过check），然后就进行下一层递归，递归深度上面也说了就是看多少行，当递归到最后一行结束，我们就完成所有递归
#include<bits/stdc++.h>
using namespace std;
int n;
vector<vector<int>>res;
vector<int>path;
bool check(int row,int col){
//要记好path里面存的是每个皇后在的列数，并且对应的是第i行时候皇后所在列数//检查列for(int i=0;i<row;i++){//看看之前的行里面有没有这个列，如果有就说明这个列放过了 if(path[i]==col) return false;//当第i行的皇后在的列数等于当前第row行皇后所在的列数，
//说明皇后这一列上面出现过皇后，那就不行}
//检查45度的对角线
//如果在第i行的皇后出现的列数是j（这个for循环的遍历出来的格子就是皇后的45度对角线），那就说明这个对角线出现过皇后for (int i=row-1,j=col-1;i>=0&&j>=0;i--,j--) {if (path[i]==j) {return false;}}
//检查135度的对角线
//同理for(int i=row-1,j=col+1;i>=0&&j<n;i--,j++) {if (path[i]==j) {return false;}}return true;}
void dfs(int row){
//因为我们想要收集的是列数，但我们是从0开始的，所以在收集的时候对每一列都要加1if(row==n){vector<int> res1;for(int i:path){res1.push_back(i+1);}res.push_back(res1);return;}for(int col=0;col<n;col++){if(check(row,col)){path.push_back(col);dfs(row+1);path.pop_back();}}
}int main(){cin>>n;dfs(0);sort(res.begin(),res.end());int k=0;for(auto i:res){k++;for(int j:i){cout<<j<<' ';}if(k==3) break;cout<<endl; if(k==3) break;}cout<<endl<<res.size();}P1330 封锁阳光大学
题目描述
曹是一只爱刷街的老曹，暑假期间，他每天都欢快地在阳光大学的校园里刷街。河蟹看到欢快的曹，感到不爽。河蟹决定封锁阳光大学，不让曹刷街。
阳光大学的校园是一张由 n 个点构成的无向图，n 个点之间由 m 条道路连接。每只河蟹可以对一个点进行封锁，当某个点被封锁后，与这个点相连的道路就被封锁了，曹就无法在这些道路上刷街了。非常悲剧的一点是，河蟹是一种不和谐的生物，当两只河蟹封锁了相邻的两个点时，他们会发生冲突。
询问：最少需要多少只河蟹，可以封锁所有道路并且不发生冲突。
输入格式
第一行两个正整数，表示节点数和边数。 接下来 m 行，每行两个整数 u,v，表示点 u 到点 v 之间有道路相连。
输出格式
仅一行如果河蟹无法封锁所有道路，则输出
Impossible，否则输出一个整数，表示最少需要多少只河蟹。输入输出样例
输入 #1复制
3 3 1 2 1 3 2 3输出 #1复制
Impossible输入 #2复制
3 2 1 2 2 3输出 #2复制
1说明/提示
【数据规模】
对于 100% 的数据，1≤n≤104，1≤m≤105，保证没有重边。
思路
先说一下这题是要干啥吧 就是给一个图，如果封锁一个节点，那这个节点所连接的道路就也被封锁了，但不能封锁相邻的节点，问能不能封锁所有道路，如果能，那至少需要封锁多少节点
这是一个二分图的题，，那我们再说一下什么是二分图
如果一个无向图可以被分成两个集合，使得任意一条边都能连接这两个集合中的节点，而同一集合中的结点之间没有边，那他就是二分图，那怎么看是不是二分图，我们可以用染色，遍历图，最开始先给一个节点染成颜色1，然后开始dfs相邻的染成不同颜色也就是1-color，这样就分成两个部分了，然后你就会发现没条边的两端一定是1和0，然后你只要把其中一个集合都封锁了，那就是不是把每一条边都封锁了，并且你保证了染的节点都不相邻，
看这个图（2和3之间没边哈），1 4 是一个集合，2 3是一个集合，我们是不是就保证了所有边都连接了两个集合的所有边，
看代码啦
#include <bits/stdc++.h>
using namespace std;
int n,m;
const int N=1e5 +10;
bool visited[N];//判断是否遍历过
int colors[N]={0};//记录每个节点的颜色
int sum[2];//存储颜色节点的数量
//检查图的连接组件是否为二分图，如果是，则给节点上色。如果组件是二分图，则返回true，否则返回false
bool dfs(int node,int color,vector<vector<int>>&graph) {//不会进入无线循环，因为我们要判断的就是把每个节点都走走完他走的，看看对于这个节点来说，他的颜色是不是还是这个if (visited[node]) {if (colors[node] == color) return true;//如果遇到已经访问过的，并且现在要给他染的颜色与之前染过的一样，那就是truereturn false;}visited[node] = true;//没访问的话，那现在访问了colors[node] = color;sum[colors[node]] += 1;//属于这个颜色的节点就增多一个bool flag = true;//最初先设为是二分图//把所有节点都遍历一遍原因是，我们要判断每个节点的相邻是否跟她一样，不理解的话就脑子里想个奇数环，就一个三角形的环就行for (auto v:graph[node]) {//遍历所有节点flag = flag && dfs(v,1-color,graph);//如果从这个节点去遍历染色，不能染染成两个集合，那就最后肯定被false}return flag;}
int main() {cin>>n>>m;vector<vector<int>>graph(n+1);while (m--) {int u,v;cin>>u>>v;//题上说无向图graph[u].push_back(v);graph[v].push_back(u);}int ans=0;//每个都要遍历一次，因为只遍历一个节点，可能无法到达所有地方//其实也就是防止有多个图for (int i=1;i<=n;i++) {if (!visited[i]) {sum[0]=sum[1]=0;if (!dfs(i,0,graph)) {//如果这个节点没被遍历过cout<<"Impossible"<<endl;}return 0;ans+=min(sum[0],sum[1]);}}cout<<ans;
}P1118 [USACO06FEB] Backward Digit Sums G/S
题目描述： 农夫约翰和他的奶牛们喜欢玩一个智力游戏。他们将 1 到 N (1 <= N <= 10) 的数字以某种顺序写下来，然后将相邻的数字相加，得到一个数字个数比原来少 1 的新列表。他们重复这个过程，直到只剩下一个数字。例如，当 N=4 时，游戏的一个例子可能是这样的：
3 1 2 44 3 67 916在农夫约翰的背后，奶牛们开始玩一个更难的游戏，她们只知道最终的总和和数字 N，就试图确定起始序列。不幸的是，这个游戏有点超出农夫约翰的智力算术能力。
编写一个程序来帮助农夫约翰玩这个游戏，跟上奶牛们的步伐。
输入格式： 第一行：两个空格分隔的整数：N 和最终的总和。
输出格式： 第一行：一个 1..N 的整数的排序，使得它能够得到给定的总和。如果有多个解决方案，选择字典序最小的一个，即把较小的数字放在前面。
输入样例： 4 16
输出样例： 3 1 2 4
说明/提示： 对于 40% 的数据，1 <= n <= 7； 对于 80% 的数据，1 <= n <= 10； 对于 100% 的数据，1 <= n <= 12, 1 <= sum <= 12345。
思路
注意看，这是杨辉三角，（当然我没看出来，我看题解，> <）
你看，是不是就是左边加右边那个的和然后弄到下面，，我们要求的组合一定是这个组合对应的数乘杨辉三角的系数，看题给的例子，是不是就是3*1+1*3+2*3+4*1，是不是乘的就是1 3 3 1，
看代码啦，这个代码是看的题解写的因为我最开始并没有往杨辉三角想
#include <bits/stdc++.h>
using namespace std;
int n,sum;
bool visited[25];
int ans[25];
int pc[25];//用来构造杨辉三角
//i代表已经枚举了钱i个数，数的序号是从1开始
//num表示第i个数是num
//w代表前i个数1的总和
bool dfs(int i,int num,int w) {if (w>sum) {return false;}//如果搜到最后一个的话看看是不是满足sum不满足就false，满足就returnif (i==n) {if (w==sum) {ans[i]=num;return true;}return false;}visited[num]=true;//第i个数的值已经使用过了，因为一个数只能用一次for (int j=1;j<=n;j++) {//开始试第i个数哪个合适，把1到n都试一遍//这里第三个参数这样写，是因为我们找的组合一定是杨辉三角系数和这个组合对应的乘积if (!visited[j]&&dfs(i+1,j,w+pc[i]*j)) {ans[i]=num;return true;}}visited[num]=false;//回溯一下return false;//执行到这里就说明没有找到合适的组合
}
int main() {cin>>n>>sum;pc[0]=pc[n-1]=1;for (int i=1;i*2<n;i++) {pc[i]=pc[n-1-i]=(n-i)*pc[i-1]/i;//杨辉三角的公式}if (dfs(0,0,0)) {//如果搜索到了合适的值就直接输出就行，因为哦我们是从0开始搜并且每一位的数也是从1开始遍历//字典序当然是最小的for (int i=1;i<=n;i++) {cout<<ans[i]<<" ";}return 0;}
}P2052 [NOI2011] 道路修建
题目描述
在 W 星球上有 n 个国家。为了各自国家的经济发展，他们决定在各个国家之间建设双向道路使得国家之间连通。但是每个国家的国王都很吝啬，他们只愿意修建恰好 n−1 条双向道路。
每条道路的修建都要付出一定的费用，这个费用等于道路长度乘以道路两端 的国家个数之差的绝对值。例如，在下图中，虚线所示道路两端分别有 2 个、4 个国家，如果该道路长度为 1，则费用为 1×∣2−4∣=2。图中圆圈里的数字表示国家的编号。
由于国家的数量十分庞大，道路的建造方案有很多种，同时每种方案的修建费用难以用人工计算，国王们决定找人设计一个软件，对于给定的建造方案，计算出所需要的费用。请你帮助国王们设计一个这样的软件。
输入格式
输入的第一行包含一个整数 n，表示 W 星球上的国家的数量，国家从 1 到 n 编号。
接下来 n–1 行描述道路建设情况，其中第 i 行包含三个整数 ai,bi 和 ci，表示第 i 条双向道路修建在 ai 与 bi 两个国家之间，长度为 ci。
输出格式
输出一个整数，表示修建所有道路所需要的总费用。
输入输出样例
输入 #1复制
6 1 2 1 1 3 1 1 4 2 6 3 1 5 2 1输出 #1复制
20说明/提示
对于 100% 的数据，1≤ai,bi≤n，0≤ci≤106，2≤n≤106。
测试点编号 n= 1 2 2 10 3 100 4 200 5 500 6 600 7 800 8 1000 9 104 10 2×104 11 5×104 12 6×104 13 8×104 14 105 15 6×105 16 7×105 17 8×105 18 9×105 19,20 106
思路
用一个size数组记录每个节点的大小（带上自己以及自己孩子的节点数量），然后从第一个节点开始搜索，通过dfs吧每一个桥的大小给加起来就行，，，需要注意的是这题的节点数量n范围很大，最大1e6，用邻接表的话速度会标慢，一定被卡，因为我就一直被卡，所以要用链式前向星
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n;
const int N = 1e7+10;
int sizes[N];
int ans;
int head[N],cnt;
//建图
struct edge {int to;//代表这条边指向的目标定点，也就是这个边的终点 int next;//当前边的下一条边号 int w;// 这条边的权重，（如距离，成本之类的）
}graph[N*2];//N是节点的数量，通常边是节点的两倍，因为无向图，要存两次边
void add_edge(int u, int v, int w) {cnt++;//cnt是边的计数器，表示已经添加边的数量，每次调用要记得++，这次是最开始++//因为这次的节点是从1开始的 graph[cnt].to = v;//边的终点是v graph[cnt].w = w;//下面两个是头插法，插的是边号 graph[cnt].next = head[u];head[u] = cnt;
}
// 子节点 父节点
void dfs(int x,int fa)
{sizes[x]=1;for(int i=head[x];i;i=graph[i].next)//我们初始化的head数组都是0,所以当我们碰到i是0时候就说明我们x节点所连接的所有节点已经遍历完了{int to=graph[i].to;if(fa==to) continue;dfs(to,x);sizes[x]+=sizes[to];ans+=graph[i].w*abs(2*sizes[to]-n);}
}
signed main() {scanf("%lld",&n);for (int i=1;i<n;i++) {int u,v,w;scanf("%lld%lld%lld",&u,&v,&w);add_edge(u,v,w);add_edge(v,u,w);}dfs(1,0);cout<<ans<<endl;
}顺便说一下这个链式前向星吧，可能有人不知道怎么弄，他有点类似链表，直接看代码和注释吧，靠，奋战30分钟，发现我讲不出来这个链式前向星，只能自己搜视频自己悟去吧，骚瑞反正链式前向星就是遍历边的隔了几天突然又懂了，你看dfs函数里面那个for循环遍历，他是从x节点头边开始遍历这个节点的所有边，然后通过得到to也就是这个边连接的另一个节点开始dfs遍历这个to，这样我们就能把整个图给遍历一遍咯，
P2196 [NOIP 1996 提高组] 挖地雷
题目描述
在一个地图上有 N (N≤20) 个地窖，每个地窖中埋有一定数量的地雷。同时，给出地窖之间的连接路径。当地窖及其连接的数据给出之后，某人可以从任一处开始挖地雷，然后可以沿着指出的连接往下挖（仅能选择一条路径），当无连接时挖地雷工作结束。设计一个挖地雷的方案，使某人能挖到最多的地雷。
输入格式
有若干行。
第 1 行只有一个数字，表示地窖的个数 N。
第 2 行有 N 个数，分别表示每个地窖中的地雷个数。
第 3 行至第 N+1 行表示地窖之间的连接情况：
第 3 行有 n−1 个数（0 或 1），表示第一个地窖至第 2 个、第 3 个 … 第 n 个地窖有否路径连接。如第 3 行为 11000⋯0，则表示第 1 个地窖至第 2 个地窖有路径，至第 3 个地窖有路径，至第 4 个地窖、第 5 个 … 第 n 个地窖没有路径。
第 4 行有 n−2 个数，表示第二个地窖至第 3 个、第 4 个 … 第 n 个地窖有否路径连接。
……
第 n+1 行有 1 个数，表示第 n−1 个地窖至第 n 个地窖有否路径连接。（为 0 表示没有路径，为 1 表示有路径）。
输出格式
第一行表示挖得最多地雷时的挖地雷的顺序，各地窖序号间以一个空格分隔，不得有多余的空格。
第二行只有一个数，表示能挖到的最多地雷数。
输入输出样例
输入 #1复制
5 10 8 4 7 6 1 1 1 0 0 0 0 1 1 1输出 #1复制
1 3 4 5 27
思路：
这题是有向图，就相当于遍历树没因为咱这个专题是dfs加训，所以我就直接暴力写了，还可以用dp但现在就先不写了哈哈（其实我还没怎么掌握dp），，，这题呢就是从每个节点遍历，然后看看哪个节点遍历的值最大，然后存一下他这个路径和值，用一个path全局数组存路径，利用回溯然后存的每一次的dfs遍历的节点，再用res数组存的最后最大的值的路径，具体看代码就行
这题是在朋友家，我看着他写的，他用的字符串存的路径，然后我回家改了一下（因为他懒得给我再用数组存了）
#include <bits/stdc++.h>
using namespace std;#define int long long
const int N = 1e5 + 10;
int n;
int w[N];
vector<int> g[30];
vector<int>path;
int mx = 0;
vector<int>res;void dfs(int now,int ans){if(g[now].size() == 0){if(mx < ans){res=path;mx = ans;}return; }for(int v : g[now]){path.push_back(v);dfs(v, ans + w[v]);path.pop_back();}
}
void solve(){cin >> n;for(int i = 1; i <= n; i++){cin >> w[i];}for(int i = 1; i < n; i++){for(int j = i + 1; j <= n; j++){int u;cin >> u;if(u == 1){g[i].push_back(j);}}} for(int i = 1; i <= n; i ++){ path.push_back(i);dfs(i, w[i]); path.pop_back();}for(auto i:res)cout<<i<<" "; cout << '\n';cout << mx << '\n';}
signed main(){solve();
}P2420 让我们异或吧
题目描述
异或是一种神奇的运算,大部分人把它总结成不进位加法.
在生活中 xor 运算也很常见。比如，对于一个问题的回答，是为 1，否为 0，那么：
（A 是否是男生）xor（B 是否是男生）＝ A 和 B 是否能够成为情侣
好了，现在我们来制造和处理一些复杂的情况。比如我们将给出一颗树，它很高兴自己有 N 个结点。树的每条边上有一个权值。我们要进行 M 次询问，对于每次询问，我们想知道某两点之间的路径上所有边权的异或值。
输入格式
输入文件第一行包含一个整数 N ，表示这颗开心的树拥有的结点数，以下有 N−1 行，描述这些边，每行有3个数，u,v,w，表示 u 和 v 之间有一条权值为 w 的边。接下来一行有一个整数 M，表示询问数。之后的 M 行，每行两个数 u,v，表示询问这两个点之间的路径上的权值异或值。
输出格式
输出 M 行，每行一个整数，表示异或值
输入输出样例
输入 #1复制
5 1 4 9644 2 5 15004 3 1 14635 5 3 9684 3 2 4 5 4 1 1输出 #1复制
975 14675 0说明/提示
对于 40% 的数据，有 1≤N,M≤3000；
对于 100% 的数据，有 1≤N,M≤100000。保证边权在
int范围内。
思路 ：
就是直接搜索，因为他是一个树，我们只要保证他不重新搜他的父节点就行，就保证不会无限循环，我们只要在找个数组让他存每个节点在整个路径上异或出来的结果就行
比如我们从1开始遍历，3节点的异或值就是1的异或值（作为根节点异或值为0）^1到3路上的异或值，5就是1^2^(3到5路上的异或值)，就这样我们就可以求出某个节点到某个节点的路上的异或值了，比如求3到5，那就是(1到3)^(1到3)^（3^5）对吧相同就消掉，看代码吧
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
vector<pair<int,int>> graph[N];
int n;
int xor_fa[N];
void dfs(int son,int fa,int xor_sum){xor_fa[son]=xor_sum;for(auto v:graph[son]){if(v.first!=fa){dfs(v.first,son,(xor_sum^v.second));}}
}
int main(){cin>>n;n--;while(n--){int u,v,w;cin>>u>>v>>w;graph[u].emplace_back(v,w);graph[v].emplace_back(u,w);}dfs(1,-1,0);int m;cin>>m;while(m--){int u,v;cin>>u>>v;cout<<(xor_fa[u]^xor_fa[v])<<'\n';}return 0;
}P2853 [USACO06DEC] Cow Picnic S
题目描述 奶牛们要举行野餐！ Farmer John 的 K (1 ≤ K ≤ 100) 头奶牛每头都在 N (1 ≤ N ≤ 1,000) 个牧场中的一个吃草，方便地编号为 1...N。牧场之间通过 M (1 ≤ M ≤ 10,000) 条单向路径连接（没有路径将牧场连接到自身）。
奶牛们想聚集在同一个牧场进行野餐，但（由于单向路径）一些奶牛可能只能到达某些牧场。请帮助奶牛们找出所有奶牛都可以到达的牧场数量，因此这些牧场是可能的野餐地点。
输入格式 第 1 行：三个空格分隔的整数，分别为：K、N 和 M
第 2..K+1 行：第 i+1 行包含一个整数 (1..N)，该整数是奶牛 i 正在吃草的牧场的编号。
第 K+2..M+K+1 行：每行包含两个空格分隔的整数，分别为 A 和 B（均为 1..N 且 A != B），表示从牧场 A 到牧场 B 的单向路径。
输出格式 第 1 行：三个空格分隔的整数，分别为：K、N 和 M
第 2..K+1 行：第 i+1 行包含一个整数 (1..N)，该整数是奶牛 i 正在吃草的牧场的编号。
第 K+2..M+K+1 行：每行包含两个空格分隔的整数，分别为 A 和 B（均为 1..N 且 A != B），表示从牧场 A 到牧场 B 的单向路径。
输入输出样例 输入 #1复制
2 4 4 2 3 1 2 1 4 2 3 3 4 输出 #1复制
2 说明/提示 奶牛们可以在牧场 3 或 4 见面。
思路
他这个输出应该是弄错了，应该输出有几个牧场可以见面，这道题就是从k个牛最开始所在地牧场开始搜索遍历，用一个num数组存一下每个农场能搜几次，如果有能搜索k次就说明这个牧场能被那k个牛到达
#include<bits/stdc++.h>using namespace std;const int N=1010;int visited[N],farm[N],num[N];vector<int>graph[N];int k,m,n,ans;void dfs(int i){num[i]++;visited[i]=1;for(auto v:graph[i]){if(!visited[v]){dfs(v);}}}int main(){cin>>k>>n>>m;for(int i=1;i<=k;i++)cin>>farm[i];//在这些农场吃草while(m--){int u,v;cin>>u>>v;graph[u].push_back(v);} for(int i=1;i<=k;i++){memset(visited,0,sizeof(visited));dfs(farm[i]);}for(int i=1;i<=n;i++){if(num[i]==k)ans++;}cout<<ans;}B3624 猫粮规划
题目描述
到中午了，机器猫要吃猫粮了。
机器猫掏出 n 份食物，第 i 份食物含有的能量为 w[i]。机器猫可以吃掉其中一些食物，获得这些食物的能量之和。
机器猫又不想变得太胖又不想变得太瘦，所以指定了一个目标区间 [l,r]。显然，可能有很多种选择食物的方式可以达成这个目标，因此机器猫想知道方案总数。
输入格式
第一行，三个正整数 n,l,r。
第二行，n 个正整数，表示每一份食物含有的能量 w[i]。
输出格式
仅一行，一个整数，表示方案数。
输入输出样例
输入 #1复制
4 70 85 10 10 20 50输出 #1复制
4说明/提示
样例解释
所有方案如下：
选择食物 1, 2, 4，能量 10+10+50 = 70
选择食物 1, 3, 4，能量 10+20+50 = 80
选择食物 2, 3, 4，能量 10+20+50 = 80
选择食物 3, 4，能量 50+20 = 70共 4 种方案。
数据规模与约定
对于 50% 的数据，满足 n≤20。
对于 100% 的数据，满足 n≤40,20≤w[i]≤100,l≤r≤300。
提示：w[i] 在范围内均匀随机生成。
思路
就一路两搜索，然后看哪个合适就ans++就行，记得剪枝
#include<bits/stdc++.h>
using namespace std;
int l,r,n,ans;
int w[45];
void dfs(int x,int sum){if(x>n){if(sum>=l&&sum<=r) {ans++;} return;}if(sum>r||x>n) return;dfs(x+1,sum+w[x]);dfs(x+1,sum);
}
int main(){cin>>n>>l>>r;for(int i=1;i<=n;i++) cin>>w[i]; dfs(1,0);cout<<ans;
} P3848 [TJOI2007] 跳棋
题目背景
本题可能为错题，目前数据只是随机生成的 n≤20 的情况，测试数据和题解仅供参考。
在一个n×n的棋盘上，布满了0和1，如图（a）所示（n=7），为叙述方便，将0用字母表示，如图（b）。
题目描述
跳棋规则：
（1）从某个0格出发，可以向上，下，左，右4个方向连续越过若干个（至少1个）
1格而跳入下一个0格。如图（b）中从A出发，可跳到B，或者到E，但不能直接到K。在跳到B之后还可以继续跳到F;在跳到E之后可继续跳到F或K。直到不能再跳为止。
（2）每个0格只能到达一次，给出的起始点不能再到达，也不能越过。
跳过的距离为跳过1格个数加1，如从A到B，跳过距离为3，从B到F，跳过距离为2。
问 题： 当棋盘和起始点给出之后，问最远能跳的距离是多少？
如上图（b）中，从A出发，可跳过的路线不止一条，其中一条为：
A － B － F － L － K － E （可能不唯一）
3 2 3 3 3
它的距离为14。
输入格式
第一行三个整数 n（1≤n≤100），x，y（起点坐标，上图（b）中A处坐标为1，3）
接下来n行，每行n个数（0或1），数与数之间用一个空格分隔。
输出格式
一个整数，即最大可跳距离（若不能跳，输出0）。
输入输出样例
输入 #1复制
4 3 2 1 0 1 0 1 1 1 1 0 0 1 0 1 1 0 1输出 #1复制
6说明/提示
upd 2022.7.27：新增加一组 Hack 数据。
思路
就是类似于洪水填充看看上下左右哪些合适，还有就是输入格子时候，要从1,1开始，或者就是x--,y--，要不然搜不到，我后来才发现题上给的最开始的棋盘就是从1，1开始，这题看了点题解
#include<bits/stdc++.h>
using namespace std;
const int N=110;
int mv[]={-1,0,1,0,-1};
int n,x,y,ans;
int grid[N][N],visited[N][N];
void dfs(int x,int y ,int step){ans=max(ans,step);for(int i=0;i<5;i++){int s=0,nx=x,ny=y;while(nx+mv[i]>0&&nx+mv[i]<=n&&ny+mv[i+1]>0&&ny+mv[i+1]<=n){s++;nx+=mv[i];ny+=mv[i+1];if(grid[nx][ny]==0) break;}if(nx>0&&nx<=n&&ny>0&&ny<=n&&grid[nx][ny]==0&&s!=1&&!visited[nx][ny]){//能跳过去的情况//1, 跳过去的格子一定是0//2， 遇到的格子是0//3, 这个格子之前没跳过 visited[nx][ny]=1;dfs(nx,ny,step+s);visited[nx][ny]=0;}}
}int main(){cin>>n>>x>>y;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){cin>>grid[i][j];}}visited[x][y]=1;dfs(x,y,0);
cout<<ans;
} P3864 [USACO1.2] 命名那个数字 Name That Number
题目描述
在威斯康辛州牛守志大农场经营者之中，都习惯于请会计部门用连续数字给母牛打上烙印。但是,母牛本身并没感到这个系统的便利,它们更喜欢用它们喜欢的名字来呼叫它们的同伴，而不是用像这个的语句"C'mon, #4364, get along."。请写一个程序来帮助可怜的牧牛工将一只母牛的烙印编号翻译成一个可能的名字。因为母牛们现在都有手机了，使用标准的按键的排布来把将数目翻译为文字:( 除了 "Q" 和 "Z")
2: A,B,C 5: J,K,L 8: T,U,V 3: D,E,F 6: M,N,O 9: W,X,Y 4: G,H,I 7: P,R,S可接受的名字都被放在这样一个叫作"dict.txt" 的文件中，它包含一连串的少于 5,000个（准确地说是4617个）可被接受的牛的名字。 (所有的名字都是大写的且已按字典序排列) 请读入母牛的编号并返回那些能从编号翻译出来并且在字典中的名字。举例来说,编号 4734 能产生的下列各项名字: GPDG GPDH GPDI GPEG GPEH GPEI GPFG GPFH GPFI GRDG GRDH GRDI GREG GREH GREI GRFG GRFH GRFI GSDG GSDH GSDI GSEG GSEH GSEI GSFG GSFH GSFI HPDG HPDH HPDI HPEG HPEH HPEI HPFG HPFH HPFI HRDG HRDH HRDI HREG HREH HREI HRFG HRFH HRFI HSDG HSDH HSDI HSEG HSEH HSEI HSFG HSFH HSFI IPDG IPDH IPDI IPEG IPEH IPEI IPFG IPFH IPFI IRDG IRDH IRDI IREG IREH IREI IRFG IRFH IRFI ISDG ISDH ISDI ISEG ISEH ISEI ISFG ISFH ISFI 碰巧，81个中只有一个"GREG"是有效的(在字典中)。
写一个程序来对给出的编号打印出所有的有效名字，如果没有则输出NONE。编号可能有12位数字。
输入格式
第一行一行包含一个编号(长度可能从1到12)。
接下来4617行，每行一个字符串表示可以被接受的名字
输出格式
(file namenum.out)
以字典顺序输出一个有效名字的不重复列表，一行一个名字。 如果没有有效名字，输出'NONE'。 //注释：似乎数字只有8^4种排列（1与0不能用）
输入输出样例
输入 #1复制
4734 NMSL GREG LSDC ....(太多了不写了)输出 #1复制
GREG
思路
看完就会发现其实就是一个全排列问题，只不过这个排列的是字符，这次的dfs的深度就是输入的id的长度，上一篇文章里就说到过，比如提上说要对4617，进行全排列，那就是四个for循环在这里变化没然后组成不同的字符串看代码吧，应该能看懂
#include<bits/stdc++.h>
using namespace std;
string id;
string arr[10]={" "," ","ABC","DEF","GHI","JKL","MNO","PRS","TUV","WXY"};
set<string>ss;//可接受的字符串
vector<string> res;
string s;
void dfs(int index){if(index==id.size()){res.push_back(s);return;}int digit=id[index]-'0';string letter=arr[digit];for(int i=0;i<letter.size();i++){s.push_back(letter[i]);dfs(index+1);s.pop_back();}
}
int main(){cin>>id;for(int i=0;i<4617;i++){string p;cin>>p;ss.insert(p);} dfs(0);int flag=0;for(int i=0;i<res.size();i++){if(ss.count(res[i])){cout<<res[i]<<endl;flag=1;}}if(flag==0) cout<<"NONE";
}
P3884 [JLOI2009] 二叉树问题
题目描述
如下图所示的一棵二叉树的深度、宽度及结点间距离分别为：
- 深度：4
- 宽度：4
- 结点 8 和 6 之间的距离：8
- 结点 7 和 6 之间的距离：3
其中宽度表示二叉树上同一层最多的结点个数，节点 u,v 之间的距离表示从 u 到 v 的最短有向路径上向根节点的边数的两倍加上向叶节点的边数。
给定一颗以 1 号结点为根的二叉树，请求出其深度、宽度和两个指定节点 x,y 之间的距离。
输入格式
第一行是一个整数，表示树的结点个数 n。
接下来 n−1 行，每行两个整数 u,v，表示树上存在一条连接 u,v 的边。
最后一行有两个整数 x,y，表示求 x,y 之间的距离。
输出格式
输出三行，每行一个整数，依次表示二叉树的深度、宽度和 x,y 之间的距离。
输入输出样例
输入 #1复制
10 1 2 1 3 2 4 2 5 3 6 3 7 5 8 5 9 6 10 8 6
输出 #1复制
4 4 8
说明/提示
对于全部的测试点，保证 1≤u,v,x,y≤n≤100，且给出的是一棵树。保证 u 是 v 的父结点。
思路
因为之前没写过最近公共祖先问题嘛，就拿题解去学了一下，然后那个让算u和v直接的距离那个，我是真没看懂题目说的啥意思，就直接让题解答函数复制过来了，然后再说一下求公共祖先，就是俩兄弟看他俩深度谁最低就找那个兄弟他爹，然后就一直往上找，利用father数组，这个数组记录单是每个节点他爹是哪个节点，（利用dfs求的这个数组）
#include<bits/stdc++.h>
using namespace std;
const int N=110;
vector<int>graph[N];
int n;
int depth[N],fa[N],wide[N];
//利用dfs求出每个节点的深度
void dfs(int son,int father){fa[son]=father;depth[son]=depth[father]+1;for(auto v:graph[son]){if(v!=father){dfs(v,son);}}
}
//找到这俩兄弟最近的公共祖先
int lca(int bro1,int bro2){while(bro1!=bro2){if(depth[bro1]>=depth[bro2]){bro1=fa[bro1];}else{bro2=fa[bro2];}}return bro1;
}
//求出u和v直接的距离
int getdis(int x,int y)
{return (depth[x]-depth[lca(x,y)])*2+depth[y]-depth[lca(x,y)];
}
int main(){cin>>n;for(int i=1;i<n;i++){int u,v;cin>>u>>v;graph[u].push_back(v);graph[v].push_back(u); }dfs(1,0);//算出最深深度，也就是二叉树的深度 int max_depth=0;for(int i=1;i<=n;i++){max_depth=max(max_depth,depth[i]);wide[depth[i]]++;//同一深度的节点的数量加1 }//算出二叉树的宽度 int max_wide=0;for(int i=1;i<=max_depth;i++){max_wide=max(max_wide,wide[i]);} int u,v;cin>>u>>v;cout<<max_depth<<endl<<max_wide<<endl<<getdis(u,v);}P3915 树的分解
题目描述
给出 N 个点的树和 K，问能否把树划分成 KN 个连通块，且每个连通块的点数都是 K。
输入格式
第一行，一个整数 T，表示数据组数。接下来 T 组数据，对于每组数据：
第一行，两个整数 N,K。
接下来 N−1 行，每行两个整数 Ai,Bi，表示边 (Ai,Bi)。点用 1,2,…,N 编号。
输出格式
对于每组数据，输出
YES或NO。输入输出样例
输入 #1复制
2 4 2 1 2 2 3 3 4 4 2 1 2 1 3 1 4输出 #1复制
YES NO说明/提示
对于 60% 的数据，1≤N,K≤103；
对于 100% 的数据，1≤T≤10，1≤N,K≤105。
思路
让你划分这些区域，首先他要是奇数肯定就不对了这个先排除，再看数据，给了1e5，我们优先选择链式前向星建图，当然这个题用邻接表也过了，都行。然后我们怎样划分呢，题上说要把互粉后的区域的点数保证都是k，所以我们哟啊计算每个子树的总节点，我们设一个size数组来记录，这个size数组上面有道题也用上了，是道路修建那题，然后当我们搜索到这个子树。我们就把这个子树给砍掉，也就是让她的size为0，防止之后再累加上去出现bug，
就是这样砍，第一个图砍了后，3的size等于0，那么就不会影响2的size（如果不让3的size为0那2的size就会加上去累加），看代码吧，对了，注意每次测试用例我们必须把有关变量清0，不然会影响下一次，还有输入数据时候是输入n-1个而不是n个，我就因为这一直在找bug
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int size[N];
struct edge{int to;int next;
}graph[N*2];
int head[N],cnt;
int n,k,ans;
void add_edge(int u,int v){cnt++;graph[cnt].to=v;graph[cnt].next=head[u];head[u]=cnt;}
void dfs(int x,int fa){size[x]=1;for(int i=head[x];i;i=graph[i].next){int to=graph[i].to;if(to!=fa){dfs(to,x);size[x]+=size[to];}}if(size[x]==k){//把这个子树直接给剪了 size[x]=0;ans++;}
}
int main(){int t;cin>>t;while(t--){ memset(head, 0, sizeof(head));memset(size, 0, sizeof(size));cin>>n>>k;cnt=0;ans=0;for(int i=0;i<n-1;i++){int u,v;cin>>u>>v;add_edge(u,v);add_edge(v,u);}dfs(1,0);if(ans==n/k){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}}return 0;
}B4016 树的直径
题目描述
给定一棵 n 个结点的树，树没有边权。请求出树的直径是多少，即树上的最长路径长度是多少。
输入格式
第一行输入一个正整数 n，表示结点个数。
第二行开始，往下一共 n−1 行，每一行两个正整数 (u,v)，表示一条边。
输出格式
输出一行，表示树的直径是多少。
输入输出样例
输入 #1复制
5
1 2
2 4
4 5
2 3输出 #1复制
3
说明/提示
数据保证，1≤n≤105。
思路
还是首先看数据，1e5了咱用链式前向星吧,这道题也是有一点点意思的，先用一次搜索找到离根节点最远的节点，dfs函数里搞个depth参数，来记录每个节点的的深度，然后再用全局变量分别记录最大深度和最远节点，搜索的时候来更新记录这俩变量，看代码吧哈哈
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
struct edge{int to;int next;
}graph[N*2];
int cnt,head[N];
void add_edge(int u,int v){cnt++;graph[cnt].to=v;graph[cnt].next=head[u];head[u]=cnt;}
int max_depth,max_point;//最大深度和最远节点
void dfs(int s,int fa,int depth){if(depth>max_depth){max_depth=depth;max_point=s;}for(int i=head[s];i;i=graph[i].next){int to=graph[i].to;if(to!=fa){dfs(to,s,depth+1);}}
}
int main(){int n;cin>>n;for(int i=1;i<n;i++){int u,v;cin>>u>>v;add_edge(u,v);add_edge(v,u);}//第一次搜索，找到最远节点max_point max_depth=-1;dfs(1,-1,0);//第二次搜索，从max_point找到直径max_depth=-1;dfs(max_point,-1,0);cout<<max_depth;
} P4017 最大食物链计数
题目背景
你知道食物链吗？Delia 生物考试的时候，数食物链条数的题目全都错了，因为她总是重复数了几条或漏掉了几条。于是她来就来求助你，然而你也不会啊！写一个程序来帮帮她吧。
题目描述
给你一个食物网，你要求出这个食物网中最大食物链的数量。
（这里的“最大食物链”，指的是生物学意义上的食物链，即最左端是不会捕食其他生物的生产者，最右端是不会被其他生物捕食的消费者。）
Delia 非常急，所以你只有 1 秒的时间。
由于这个结果可能过大，你只需要输出总数模上 80112002 的结果。
输入格式
第一行，两个正整数 n、m，表示生物种类 n 和吃与被吃的关系数 m。
接下来 m 行，每行两个正整数，表示被吃的生物A和吃A的生物B。
输出格式
一行一个整数，为最大食物链数量模上 80112002 的结果。
输入输出样例
输入 #1复制
5 7 1 2 1 3 2 3 3 5 2 5 4 5 3 4输出 #1复制
5说明/提示
各测试点满足以下约定：
【补充说明】
数据中不会出现环，满足生物学的要求。（感谢 @AKEE ）
思路：
这道题很明显是有向图，我们需要在食物网中找到所有的食物链，也就是找到所有的路径，因为我们专题是dfs嘛，而且我也好久没写拓扑排序的题了，对这玩意也快忘了，就用dfs讲吧，先说一下dfs设的含义，就是到达节点x时候还能选择走几条路，这里用了记忆化搜索，就是用一个数组存下走到每个节点时候的值，因为暴力搜索会走很多次ii昂通道路，我们就可以用一个数组来保存这个走过的路，如果这个路走过我们直接返回这个值就好，这样就大大减少了时间复杂度，还有数据大小也要注意别少开了，具体解析代码注释上有
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
struct edge{int to;int next;
}graph[N];
int head[N],cnt,in_degree[N],out_degree[N];//in代表这个节点是否被吃过，out代表这个否吃过别的节点
//因为我们的dfs停止条件必须是当遇到生产者，因为生产者只能被吃，所以用out就可以找到哪个节点没吃过别的节点
//in可以找到没被吃的，这个就是最高营养级，没被别的节点吃过，我们就要从这个节点开始dfs
void add_edge(int a,int b){cnt++;graph[cnt].to=b;graph[cnt].next=head[a];head[a]=cnt;
}
int n,m,dp[5010];
int dfs(int x){if(out_degree[x]==0){//如果x没吃过，他就是生产者，dfs也就到尽头了return 1;//走完这条路，那就返回1 }if(dp[x]!=0){return dp[x];}int count=0;//记录当前节点所能选择的路的个数 for(int i=head[x];i;i=graph[i].next){count=(count+dfs(graph[i].to))%80112002;}dp[x]=count;return count;}
int ans;
int main(){cin>>n>>m;while(m--){int u,v;cin>>v>>u;add_edge(u,v);//u没被吃，u连接的节点是自己吃的节点in_degree[v]=1;out_degree[u]=1;}for(int i=1;i<=n;i++){if(in_degree[i]==0){ans=(ans+dfs(i))%80112002;//可能不止有一个最高营养级的生物，所以要加起来 }}cout<<ans;
}完结，，也是写了好长时间，中间摆烂了几天一直没学习，写得多了后看dfs大概的套路差不多是知道了，但是有的题还是需要读出来那个题眼，我们才能用dfs去得到我那要的东西，，之后还会继续写一下bfs，dijkstra算法，Floyd等等，这些关于最短路的，