笔试题笔记#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;
}