DFS

#include <bits/stdc++.h>
using namespace std;
void dfs(int x/*定义递归所需参数*/){
	if(/*结束条件成立*/){
		//记录结果 
		//其他...
		return; 
	}
	//剪枝（可选） 
	for(/*枚举扩展状态*/){
		//如果可行，就递归下去
		dfs(newx);
		//回溯（根据题目需要决定） 
	}
}
int main(){
	dfs();
	return 0;
}

BFS

#include <bits/stdc++.h>
using namespace std;
struct stu{
	int x,y;
	//如果是二维，就定义 x,y
	//如果是一维，就定义 x
	//如果求最短路径，就定义 step记录步数 
};
void bfs(){
	//初始化部分 
	queue<stu> q;//建队
	q.push();//初始状态入队
	//起点打标记（根据题目需要决定）
	//其他... 
	while(!q.empty()){//只要队列不为空
		stu fr=q.front;//取出队首
		q.pop();//弹首
		//判断结束条件（根据题目需要决定） ，符合就结束BFS 
		//剪枝（可选）
		for(/*枚举扩展状态*/){
			//记忆化，打标记（根据题目需要决定）
			q.push();//入队
			//其他... 
		} 
		cout<<"No Answer!";//能运行到这说明没有符合条件的数（可选） 
	}
}
int main(){
	bfs();
	return 0;
}

拓扑排序

方法一

void toposort() {
	for(int i=1; i<=n; i++) {
		if(d[i]==0)q.push(i);//入度为0的节点入队
	}
	while(!q.empty()) {
		int u=q.front();
		a[++len]=u;//len用于统计整个过程中遍历的节点总数
		q.pop();
		for(int i=0; i<G[u].size(); i++) {
			int v=G[u][i];
			d[v]--;//v入度减1，即删去u节点及其所有出边
			if(d[v]==0) {
				q.push(v);
			}
		}
	}
	if(len!=n) {
		cout<<"the graph has cycle."<<endl;
	} else {
		for(int i=1; i<=len; i++)cout<<a[i]<<" ";
	}
}

方法二DFS实现

void dfs(int u) {
	vis[u]=1;//标记节点正在访问中
	for(int i=0; i<G[u].size(); i++) {
		int v=G[u][i];
		if(vis[v]==1) { //访问到正在访问的节点，说明存在环。拓扑排序无法继续开展
			cout<<"the graph has cycle."<<endl;
			exit(0);
		}
		if(vis[v]==0) { //未访问过的节点
			dfs(v);
		}
	}
	vis[u]=-1;//该节点访问结束
	s.push(u);//用栈存储访问结束的节点，通过输出弹出栈顶，还原节点访问顺序
}

推荐方法二

总模板

#include <bits/stdc++.h>
using namespace std;
int n,vis[1005],a; 
vector<int> g[1005];
stack<int> s;
void dfs(int u) {
	vis[u]=1;
	for(int i=0; i<g[u].size(); i++) {
		int v=g[u][i];
		if(vis[v]==1){
			exit(0);
		}
		if(vis[v]==0) {
			dfs(v);
		}
	}
	vis[u]=-1;
	s.push(u);
}
int main(){
	cin>>n;
	//输入部分
	//dfs部分 
	while(!s.empty()){
		cout<<s.top()<<' ';
		s.pop();
	}//输出 
	return 0;
}

最小生成树（并查集+Kruskal算法）

#include <bits/stdc++.h>
using namespace std;
const int N=5005,M=2e5+5;
int n,m,fa[N],cnt,sum;
struct edge{
	int u,v,w;
	bool operator < (const edge &y)const{
		return w<y.w;
	}
};
int find(int x){
	if(fa[x]!=x){
		fa[x]=find(fa[x]);
	}
	return fa[x];
}
edge g[M];
//bool cmp(edge x,edge y){return x.w<y.w;}

int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)fa[i]=i;
	for(int i=1;i<=m;i++)
		cin>>g[i].u>>g[i].v>>g[i].w;
	sort(g+1,g+m+1);
	//sort(g+1,g+m+1,cmp);
	for(int i=1;i<=m;i++){
		int u=g[i].u,v=g[i].v,w=g[i].w;
		int x=find(u),y=find(v);
		if(x==y)continue;
		cnt++;
		sum+=w;
		fa[x]=y;//f[y]=x;f[x]=f[y]
		if(cnt==n-1)break;
	}
	if(cnt!=n-1)cout<<"orz";//
	else cout<<sum;
	return 0;
}