邻接矩阵的深度优先遍历(dfs)
描述：
共有N个城市编号1到N和M条路编号1到M。
第i条路可以从城市Ai通往通往Bi，但不能从Bi通往Ai。
你计划从某个城市出发经过X（X≥0）条路到某个城市，即计划从某个城市经过任意条路到另一个城市，终点可以是出发的城市。
请计算有多少对城市可以作为你的起点和终点。
输入：
第一行为N和M。
接下来M行，每行有一对城市Ai和和Bi；
输出：
请计算有多少对城市可以作为你的起点和终点。
数据范围：
2≤N≤2000
0≤M≤min(2000,N(N−1))
1≤Ai,Bi≤N
Ai≠Bi
#include<bits/stdc++.h> using namespace std; typedef unsigned long long ull; typedef long long ll; const ll maxx = 1e18; const int N = 1e6+10; const int p = 1e4; const double eps = 1e-8; int n,m; int G[2001][2001];//邻接矩阵存图 int a,b,cnt;//全局变量 cnt 记录个数 bool flag[2001];//记录每个城市是否走过 void dfs(int k) { cnt++; flag[k]=1;//每到一个点把此点标记并且记录个数 for(int i=1;i<=n;i++) { if(flag[i]==0&&G[k][i]==1) { dfs(i); } }//搜索所有的情况 ，注意走不到的点 和 已经走过的点不可以作为终点 } int main() { cin>>n>>m; for(int i=1;i<=m;i++) { cin>>a>>b; G[a][b]=1; }//存矩阵，可走的为 1 ，不可走的为 0，注意是单向路; for(int i=1;i<=n;i++) { memset(flag,0,sizeof(flag));//注意每次开始搜索的时候要初始化 flag 数组； dfs(i); }//搜索每个点，计算每个点作为起点对个数的贡献 cout<<cnt; return 0; }//此题不可用回溯算法，注意思考区别，回溯算法计数会重复
邻接矩阵的广度优先遍历
题目描述：一个图有n个节点编号从0至n−1和m条边编号从0至m−1。 输出从点x开始的广度优先遍历顺序。
输入：第一行为n,m,x。
接下来m行每行有一组u,v。表示点u可以到达点v，点v也可以到达点u。
输出：输出经过点的顺序。（输出字典序最小的答案）
#include<bits/stdc++.h> using namespace std; typedef unsigned long long ull; typedef long long ll; const ll maxx = 1e18; const int N = 1e6+10; const int p = 1e4; const double eps = 1e-8; int G[2001][2001];//邻接表 int n,m,x; int a,b,k; queue<int>qu; bool flag[2001];//一个点可能被多次走过，标记一下 int main() { cin>>n>>m>>x; for(int i=1;i<=m;i++) { cin>>a>>b; G[a][b]=1; G[b][a]=1; }//存矩阵，注意是双向路 qu.push(x); flag[x]=1;//用队列实现 bfs，存入起始点 while(!qu.empty()) { int k=qu.front(); qu.pop(); cout<<k<<" ";//每次取出队首元素输出，让队首出队 for(int i=0;i<=n-1;i++) { if(G[k][i]==1&&!flag[i]) { flag[i]=1; qu.push(i); }//找到这个点能走到的点 并且 没走过的点 ，标记一下放入队尾，从小到大搜索恰好实现了字典序最小 } } return 0; }
注意队列用 front 不用 top
