1、排列论文
#include<bits/stdc++.h>
using namespace std;
const int N=105;
vector<int>g[N];
int a[N];
int n,m;
int flag;
int topSort(){queue<int>q;for(int i=1;i<=n;i++){if(a[i]==0){q.push(i);}}int cnt=0;flag=1;while(!q.empty()){int t=q.front();q.pop();cnt++;if(!q.empty())flag=2;for(int i=0;i<g[t].size();i++){int x=g[t][i];a[x]--;if(a[x]==0)q.push(x);}}if(cnt<n)flag=0;return flag;
}
int main(){while(cin>>n>>m){for(int i=1;i<=n;i++){g[i].clear();a[i]=0;}for(int i=1;i<=m;i++){int u,v;cin>>u>>v;a[v]++;g[u].push_back(v);}int result=topSort();if(result==0)cout<<"0\n";else if(result==1)cout<<"1\n";else if(result==2)cout<<"2\n";}return 0;
}
2、十进制到二进制的转换
#include<bits/stdc++.h>
using namespace std;
int main(){int n;cin>>n;if(n<0){cout<<0<<endl;return 0;}int a[45];int idx=0;while(n>0){a[idx]=n%2;n=n/2;idx++;}for(int i=idx-1;i>=0;i--){cout<<a[i];}cout<<endl;return 0;
}
3、周末舞会
#include<bits/stdc++.h>
using namespace std;
int main(){int boy,girl,k;cin>>boy>>girl>>k;queue<int>b_q,g_q;for(int i=1;i<=boy;i++){b_q.push(i);}for(int i=1;i<=girl;i++){g_q.push(i);}while(k--){int x,y;x=b_q.front();b_q.pop();y=g_q.front();g_q.pop();cout<<x<<" "<<y<<endl;b_q.push(x),g_q.push(y);}return 0;
}
4、哥德巴赫猜想
#include<bits/stdc++.h>
using namespace std;
bool ss(int x){if(x<2)return false;for(int i=2;i*i<=x;i++){if(x%i==0){return false;}}return true;
}
int main(){int n,ans;while(cin>>n){ans=0;if(n==0)break;for(int i=2;i<=n/2;i++){if(ss(i)&&ss(n-i)){ans++;}}cout<<ans<<endl;}return 0;
}
5、查找二叉树
#include<bits/stdc++.h>
using namespace std;
const int N=105;
struct node{int value;int left;int right;
}a[N];
int n;
int target;
int cnt=0;
int result=-1;
void zhongxu(int idx){if(idx==0)return;zhongxu(a[idx].left);cnt++;if(a[idx].value==target){result=cnt;}zhongxu(a[idx].right);
}
int main(){cin>>n;cin>>target;for(int i=1;i<=n;i++){cin>>a[i].value>>a[i].left>>a[i].right;}zhongxu(1);cout<<result<<endl;return 0;
}
6、图的遍历------广度优先搜索
#include <bits/stdc++.h>
using namespace std;const int MAXN = 55;
int vis[MAXN];
int a[MAXN][MAXN];
queue<int> q;// 广度优先搜索函数
void bfs(int n) {q.push(0);vis[0] = 1;cout << 0 << " ";while (!q.empty()) {int x = q.front();q.pop();for (int i = 0; i < n; i++) {if (a[x][i] == 1 && vis[i] == 0) {vis[i] = 1;q.push(i);cout << i << " ";}}}
}int main() {int n;cin >> n;for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {cin >> a[i][j];}}bfs(n);return 0;
}
7、图的遍历------深度优先搜索
#include<bits/stdc++.h>
using namespace std;
int vis[55];
int a[55][55];
int n;void dfs(int k){vis[k]=1;cout<<k<<" ";for(int i=0;i<n;i++){if(vis[i]==0&&a[k][i]==1)dfs(i);}
}
int main(){cin>>n;for(int i=0;i<n;i++){for(int j=0;j<n;j++){cin>>a[i][j];}}dfs(0);return 0;
}
8、FBI树（二叉树）
#include <bits/stdc++.h>
using namespace std;
int a[2048+10];
int len;// 构建FBI树
void buildTree(int root) {if(root>=len)return;buildTree(2*root);buildTree(2*root+1);if(a[2*root]==1&&a[2*root+1]==1)a[root]= 1;else if(a[2*root]==0&&a[2*root+1]==0)a[root]=0;else a[root]=2;
}// 后序遍历FBI树
void dfsTree(int root) {if(root>=2*len)return;dfsTree(2*root);dfsTree(2*root+1);if (a[root]==1)cout<<"I";else if(a[root]==0)cout<<"B";else cout<<"F";
}int main() {int n;string str;cin>>n;cin>>str;len=1<<n;// 将输入的字符串存储到数组中for(int i=len;i<=2*len-1;i++){a[i]=str[i-len]-'0';}buildTree(1);dfsTree(1);return 0;
}
9、图着色问题
#include<bits/stdc++.h>
using namespace std;
const int N=510,M=N*N;
int color[N];
vector<int> g[M];
int v,m,k,n;void add(int a,int b){g[a].push_back(b);g[b].push_back(a);
}
int judge(int cnt){if(cnt!=k)return 0;for(int i=1;i<=v;i++){for(int j=0;j<g[i].size();j++){int t=g[i][j];if(color[i]==color[t])return 0;}}return 1;
}
int main(){cin>>v>>m>>k;while(m--){int a,b;cin>>a>>b;add(a,b),add(b,a);}cin>>n;for(int i=0;i<n;i++){set<int> se;//set具有去重功能for(int j=1;j<=v;j++){cin>>color[j];se.insert(color[j]);} if(judge(se.size()))cout<<"Yes"<<endl;else cout<<"No"<<endl;}return 0;
}
10、地下迷宫探索
#include <bits/stdc++.h>
using namespace std;const int N = 1005;
int vis[N];
int g[N][N];
stack<int> stk;
int n, m, src;// 深度优先搜索函数
void dfs(int k) {vis[k] = 1;if (vis[src]) cout << k;else cout << " " << k;stk.push(k);for (int i = 1; i <= n; i++) {if (!vis[i] && g[k][i] == 1) {cout << " ";dfs(i);}}stk.pop();if(!stk.empty()){cout<<" "<<stk.top();}
}int main() {memset(vis, 0, sizeof(vis));cin >> n >> m >> src; // n代表节点数，m代表边数，src代表初末位置 int s, d;for (int i = 1; i <= m; i++) {cin >> s >> d;g[s][d] = g[d][s] = 1;}dfs(src);bool connected = true;for (int i = 1; i <= n; i++) {if (!vis[i]) {connected = false;break;}}if (!connected) cout << " " << 0;return 0;
}
11、寻宝图
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+1;
int n,m,flag=0;
string map_m[N];
int cnt=0,cns=0;//cnt代表岛屿的数量，cns代表宝藏的数量
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
void dfs(int x,int y){if(x<0||x>=n||y<0||y>=m||map_m[x][y]=='0')return;if(map_m[x][y]>'1'){flag=1; } map_m[x][y]='0';for(int i=0;i<4;i++){dfs(x+dx[i],y+dy[i]);}
}
int main(){cin>>n>>m;for(int i=0;i<n;i++)cin>>map_m[i];for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(map_m[i][j]>'0'){cnt++;flag=0;dfs(i,j);//查看是否有宝藏 if(flag)cns++;}}}cout<<cnt<<" "<<cns;return 0;
}
12、信使
#include<bits/stdc++.h>
using namespace std;
const int N=105;
int n,m;
int g[N][N];
int dist[N];
bool st[N];
const int INF=0x3f3f3f3f;int dij(){memset(dist,0x3f,sizeof dist);dist[1]=0;for(int i=1;i<n;i++){int t=0;for(int j=1;j<=n;j++){if(!st[j]&&dist[j]<dist[t]){t=j;}}st[t]=true;for(int k=1;k<=n;k++){dist[k]=min(dist[k],dist[t]+g[t][k]);}}int res=0;for(int i=1;i<=n;i++){if(dist[i]==INF) return -1;res=max(res,dist[i]);}return res;
}int main(){cin>>n>>m;memset(g,0x3f,sizeof g);for(int i=1;i<=n;i++){g[i][i]=0;}for(int i=0;i<m;i++){int u,v,w;cin>>u>>v>>w;g[u][v]=min(g[u][v],w);g[v][u]=min(g[v][u],w);} cout<<dij()<<endl;return 0;
}
13、求先序排列（后中求先）
#include<bits/stdc++.h>
using namespace std;struct node{char value;node* left;node* right;node(char x):value(x),left(NULL),right(NULL){}
};//post表示后序，idx表示中序
node* buildtree(string post, string idx){if(post.empty() || idx.empty()) return NULL;// 后序遍历的最后一个字符是根节点char rootv = post.back();node* root = new node(rootv);// 在中序遍历中找到根节点的位置int rootidx = idx.find(rootv);// 分割中序遍历为左子树和右子树string leftidx = idx.substr(0, rootidx);string rightidx = idx.substr(rootidx + 1);// 分割后序遍历为左子树和右子树string leftpost = post.substr(0, leftidx.length());string rightpost = post.substr(leftidx.length(), rightidx.length());// 修正递归调用的参数顺序：(后序, 中序)root->left = buildtree(leftpost, leftidx);root->right = buildtree(rightpost, rightidx);return root;
}void xianxu(node* root){if(root == NULL) return; //直接返回，不返回值cout << root->value;xianxu(root->left);xianxu(root->right);
}int main(){string post, idx; // 修正变量名以反映实际用途cin >> idx >> post; //先输入中序，再输入后序node* root = buildtree(post, idx);xianxu(root);cout << endl;return 0;
}
14、还原二叉树
#include<bits/stdc++.h>
using namespace std;struct node{char value;node* left;node* right;// 添加构造函数node(char val) : value(val), left(NULL), right(NULL) {}
};int n;node* buildtree(string pre, string idx){if(pre.empty() || idx.empty()){return NULL;}char vroot = pre[0];node* root = new node(vroot);int idxroot = idx.find(vroot);string leftidx = idx.substr(0, idxroot);string rightidx = idx.substr(idxroot+1);string leftpre = pre.substr(1, leftidx.length());string rightpre = pre.substr(1 + leftidx.length());root->left = buildtree(leftpre, leftidx);root->right = buildtree(rightpre, rightidx);return root;
}// 修正函数名和返回值类型
int treeHeight(node* root){if(root == NULL) return 0;int leftheight = treeHeight(root->left);int rightheight = treeHeight(root->right);return max(leftheight, rightheight) + 1;
}int main(){cin >> n;string pre, idx;cin >> pre >> idx;node* root = buildtree(pre, idx); // 构建二叉树int h = treeHeight(root); // 调用修正后的函数名cout << h << endl; return 0;
}
15、求二叉树的叶子结点
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+5;
char a[N];
int cnt=0;
string str;
void dfs(int r){if(a[2*r]!=-1)dfs(2*r);cout<<a[r];if(a[2*r]==-1&&a[2*r+1]==-1){cnt++;}if(a[2*r+1]!=-1){dfs(2*r+1);}
}
int main(){cin>>str;stack<int>st;st.push(1);for(int i=0;i<str.size();i++){int p=st.top();st.pop();if(str[i]!='#'){a[p]=str[i];st.push(2*p+1);st.push(2*p);}else{a[p]=-1;}}dfs(1);cout<<"\n"<<cnt;return 0;
}
16、二叉树非叶子
#include<bits/stdc++.h>
using namespace std;
const int N=105;
struct node{int value;int left;int right;
}a[N];
int n;
void xianxu(int idx){if(idx==0)return;cout<<a[idx-1].value<<" ";xianxu(a[idx-1].left);xianxu(a[idx-1].right);
}
int main(){cin>>n;for(int i=0;i<n;i++){cin>>a[i].value>>a[i].left>>a[i].right;}for(int i=0;i<n;i++){if(a[i].left!=0&&a[i].right!=0){a[i].value+=1;}}xianxu(1);cout<<endl;return 0;
}
17.约瑟夫问题
#include<iostream>
#include<queue>
using namespace std;
int n,m;
int main(){cin>>n>>m;queue<int>q;for(int i=1;i<=n;i++){q.push(i);}int i=1;while(!q.empty()){if(i==m){cout<<q.front()<<" ";q.pop();i=1;}else{q.push(q.front());q.pop();i=i+1;}}return 0;
}
18、二叉树求高度
#include<bits/stdc++.h>
using namespace std;
const int N=105;
struct node{int data;int left;int right;
}a[N];
int n;
int dfs(int root){if(root==0)return 0;int h1=dfs(a[root].left);int h2=dfs(a[root].right);return max(h1,h2)+1;
}
int main(){cin>>n;for(int i=1;i<=n;i++){cin>>a[i].data>>a[i].left>>a[i].right;}cout<<dfs(1);return 0;
}
19、完全二叉树的权值
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int a[N];
int n,x;
int main(){int h=0,nn=0;cin>>n;for(int i=1;i<=n;i++){if(i>nn){nn+=pow(2,h);h++;}cin>>x;a[h]+=x;}int max_a=0,maxh=0;for(int i=1;i<=h;i++){if(a[i]>max_a){max_a=a[i];maxh=i;}}cout<<maxh<<endl;return 0;
}
20、围圈报数
#include<bits/stdc++.h>
using namespace std;
int main(){queue<int>cl;int n,m;cin>>n>>m;for(int i=1;i<=n;i++){cl.push(i);}while(!cl.empty()){int x;for(int i=1;i<=m-1;i++){x=cl.front();cl.pop();cl.push(x); }x=cl.front();cl.pop();cout<<x<<" ";}return 0;
}
21、走出迷宫
#include <iostream>
#include <queue>
using namespace std;char a[105][105];
int b[105][105];
int n, m;struct Node {int r, c;int step;
};int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};// 检查坐标是否在网格内
bool isValid(int r, int c) {return r >= 1 && r <= n && c >= 1 && c <= m;
}void bfs(int sr, int sc, int er, int ec) {queue<Node> dl;Node q, next;q.r = sr;q.c = sc;q.step = 0;dl.push(q);b[q.r][q.c] = 1;while (!dl.empty()) {q = dl.front();dl.pop();if (q.r == er && q.c == ec) {cout << q.step << endl; // 如果当前点是终点return;}for (int i = 0; i < 4; i++) {next.r = q.r + dir[i][0];next.c = q.c + dir[i][1];// 1可走 2未走过 3不出边界 if (a[next.r][next.c] == '.' && b[next.r][next.c] == 0 && isValid(next.r, next.c)) {next.step = q.step + 1;b[next.r][next.c] = 1;dl.push(next);}}}cout << "No path found!" << endl; // 未找到路径
}int main() {int sr, sc, er, ec;cin >> n >> m;for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {cin >> a[i][j];if (a[i][j] == 'S') {sr = i;sc = j;}if (a[i][j] == 'T') {er = i;ec = j;a[i][j] = '.'; // 将终点状态记为可走}}}bfs(sr, sc, er, ec);return 0;
}
