笔试练习记录(一)

需求：输入一行字符串，按空格进行分割，取子串存入。

#include <iostream>
#include <string>
#include <sstream>
using namespace std;
int main(){
    string str_line;
    getline(cin,str_line);
stringstream ss(str_line);
string str_tmp;
while(ss >> str_tmp)
    cout << str_tmp<<endl;
return 0;
}

练习题目

对于一个文件系统，第一行输入所有的父目录名称，第二行输入所有的子目录/文件名称，第三行输入待查询的文件或目录名称。对于查询的目录或文件名，如果存在子目录或文件，需要按输入的顺序，按层级输出所有的子目录和文件。“/”表示根目录，没有父目录。

输入描述

第一行是一个由所有的父目录名称组成的字符串，按空格分开。第二行是对应父目录的所有子目录或文件名组成的字符串，按空格分开。第三行是查询的文件名或目录名。

输出描述

按输入的顺序逐层输出所有的子目录和文件，包括查询的目录/文件本身

示例1：

输入：

/ / / home usr 
home opt env usr 1.log
home

输出：

home usr 1.log

完整代码

#include <iostream>
#include <cstring>
#include <sstream>
#include<vector>
#include<queue>
#include<string>
using namespace std;
int main(){
    vector<string> parent_dir;
    vector<string> children_dir;
    string parent_line;
    string children_line;
    string goal;
    getline(cin,parent_line);
    getline(cin,children_line);
    getline(cin,goal);
    stringstream ss1(parent_line);
    stringstream ss2(children_line);
    string str_tmp;
    while(ss1 >> str_tmp)
        parent_dir.push_back(str_tmp);
    while(ss2 >> str_tmp)
        children_dir.push_back(str_tmp);
    //输入完成
    int n = parent_dir.size();
    vector<string> ans;
    ans.push_back(goal);
    queue<string> q;
    q.push(goal);
    while(!q.empty()){
        str_tmp = q.front();q.pop();
        for(int i = 0; i < n; i++){
            if(str_tmp.compare(parent_dir[i]) == 0){
                ans.push_back(children_dir[i]);
                q.push(children_dir[i]);
            }
        }
    }
    for(auto str: ans){
        cout<<str<<' ';
    }
    cout<<endl;
        //cout << str_tmp<<endl;
    return 0;
}

需求：拓扑排序，按顺序完成事件。

练习题目

一组n个软件和k（k < (n*(n - 1)/2)）个依赖关系,若干组查询，查询两个软件的前者是否是后者的直接依赖或间接依赖。（对于[a,b]判断a是否是b的前驱节点）

输入描述

第一行输入两个正整数n和d ，代表软件的个数和依赖关系。后面d行输入相应的依赖关系。下一行输入一个正整数q，代表查询的组数。之后q行输入相应的查询。

输出描述

第一行输出q。之后q行每行输出一个正整数，如果是依赖关系，输出1，否则输出0。

示例1：

输入：

3 3
0 1
1 2
0 2
2
1 0
0 1

输出：

2
0
1

完整代码

BFS方法：

#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>
using namespace std;

bool has_dependency(unordered_map<int, vector<int>>& graph, int start, int end) {
    if (start == end) return true;
unordered_map<int, bool> visited;
queue<int> q;
q.push(start);
visited[start] = true;

while (!q.empty()) {
    int node = q.front();
    q.pop();
    
    for (int neighbor : graph[node]) {
        if (neighbor == end) {
            return true;
        }
        if (!visited[neighbor]) {
            q.push(neighbor);
            visited[neighbor] = true;
        }
    }
}

return false;
}

int main() {
    int n, d;
    cin >> n >> d;
    unordered_map<int, vector<int>> graph;
    for (int i = 0; i < d; ++i) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
    }

    int q;
    cin >> q;
    vector<pair<int, int>> queries(q);
    for (int i = 0; i < q; ++i) {
        cin >> queries[i].first >> queries[i].second;
    }

    cout << q << endl;
    for (const auto& query : queries) {
        int u = query.first, v = query.second;
        if (has_dependency(graph, u, v)) {
            cout << 1 << endl;
        } else {
            cout << 0 << endl;
        }
    }

    return 0;
}

DFS方法:

#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
using namespace std;

// 判断从 start 到 end 是否有路径
bool has_dependency(unordered_map<int, vector<int>>& graph, int start, int end, unordered_set<int>& visited) {
    if (start == end) return true;
    visited.insert(start);
    
    for (int neighbor : graph[start]) {
        if (visited.find(neighbor) == visited.end()) {
            if (has_dependency(graph, neighbor, end, visited)) {
                return true;
            }
        }
    }
    return false;
}

int main() {
    int n, d;
    cin >> n >> d;
    
    unordered_map<int, vector<int>> graph;
    for (int i = 0; i < d; ++i) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
    }
    
    int q;
    cin >> q;
    vector<pair<int, int>> queries(q);
    for (int i = 0; i < q; ++i) {
        cin >> queries[i].first >> queries[i].second;
    }
    
    cout << q << endl;
    for (const auto& query : queries) {
        int u = query.first, v = query.second;
        unordered_set<int> visited;
        if (has_dependency(graph, u, v, visited)) {
            cout << 1 << endl;
        } else {
            cout << 0 << endl;
        }
    }
    
    return 0;
}