笔试题笔记#3

1 一道bfs，唯一不同的是要对单链表中后继节点的编号排序 

#include<bits/stdc++.h>
using namespace std;const int N=10000;vector<int> headofNode[N];
int n,m;
int d;
bool st[N];
int parent[N];
vector<int> ans;void PrintAns(int i){//cout<<"PrintAns"<<endl;for(int j=i;j!=0;j=parent[j]){//cout<<j<<" ";ans.push_back(j);}ans.push_back(0);for(int k=ans.size()-1;k>0;k--){cout<<ans[k]<<"->";}cout<<ans[0];
}void bfs(){queue<int> q;q.push(0);bool isFind=false;while(!q.empty()){int t=q.front();q.pop();for(long unsigned int i=0;i<headofNode[t].size();i++){//cout<<"Nodeid"<<e[i]<<" "<<endl;int nodeid=headofNode[t][i];if(!st[nodeid]){q.push(nodeid);}if(headofNode[nodeid].size()==0&&!st[nodeid]){isFind=true;PrintAns(nodeid);break;}}if(isFind)break;}if(!isFind)cout<<"NULL";
}int main(){cin>>n;cin>>m;while(m--){int x,y;cin>>x>>y;headofNode[x].push_back(y);parent[y]=x;}//cout<<parent[1]<<endl;cin>>d;for(int i=0;i<d;i++){int x;cin>>x;st[x]=true;}for(int i=0;i<N;i++){if(headofNode[i].size()>1){sort(headofNode[i].begin(),headofNode[i].end());}}bfs();
}

2 一道bfs拓扑排序，但是记录了每个点的遍历层数 

#include<bits/stdc++.h>
using namespace std;vector<int> e[10005];  
int d[10005], dp[10005];  int main() {int n;cin >> n;for (int i = 1; i <= n; i++) {int m;  cin >> m;for (int j = 1; j <= m; j++) {int x;cin >> x;  e[x].push_back(i);  d[i]++;  }}queue<int> q;for (int i = 1; i <= n; i++) {if (d[i] == 0) {q.push(i);  dp[i] = 1;  }}while (!q.empty()) {int u = q.front();  q.pop(); for (auto v : e[u]) {dp[v] = max(dp[v], dp[u] + 1);  d[v]--;  if (d[v] == 0) {  q.push(v);  }}}int mx = 0;for (int i = 1; i <= n; i++) {if (dp[i] == 0) {  cout << -1 << endl;  return 0;}mx = max(mx, dp[i]);  }cout << mx << endl;return 0;
}