1 条题解

  • 0
    @ 2024-8-15 17:24:17

    A能击败B,意味着B会把魔杖给A,因此建一条B到A的边。建好图后,跑BFS或者DFS,找到所有从1号点出发可达的点即可。

    核心代码
    
    #include <bits/stdc++.h>
    using namespace std;
    const int N = 1e5 + 5;
    vector<int> v[N];
    int n, m;
    int x, y;
    bool vis[N];
    void dfs(int x) {
        for (int i = 0; i < v[x].size(); i++) {
            int y = v[x][i];
            if (!vis[y]) {
                vis[y] = 1;
                dfs(y);
            }
        }
    }
    int main() {
        cin >> n >> m;
        for (int i = 1; i <= m; i++) { //存图
            cin >> x >> y;
            v[y].push_back(x); //反向建边
        }
        dfs(1); //深搜
        if (v[1].empty())
            vis[1] = 1; //特判
        for (int i = 1; i <= n; i++)
            cout << vis[i]; //输出
        return 0;
    }
    
    • 1

    信息

    ID
    909
    时间
    1000ms
    内存
    256MiB
    难度
    8
    标签
    (无)
    递交数
    13
    已通过
    8
    上传者