P7370

Maysoul · 2023-05-24 10:19:11 · 题解

简单图论题目。

这个题建图的思路就是按照巫师递魔杖的顺序建边，因为在前面的是赢家，也就是说后者把魔杖递给前者，所以应建反向边。

显然无论怎么安排决斗顺序，只要这个巫师能够通过任何形式打败 1 号，那这个巫师就可能拿到魔杖，所以我们考虑通过 DFS ，找出从 1 号能否到达其他巫师就可以了。

随后我们就想到，如果一名巫师可以击败 1 号，那么 1 号无论怎么安排，都不可能拿到魔杖（好惨一巫师），所以我们建完边后，只需要考虑是否有 1 号的连边。

如果没有那 1 号有魔杖，其余无魔杖，反之则 1 号无魔杖，其余考虑 DFS 的结果即可。

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+10;
int num,ans;
vector<vector<int>> edge;
bool vis[MAXN];
void dfs(int now)
{
    for (int i:edge[now])
    {
        if(vis[i]) continue;//注意这里还要判断是否走过
        vis[i]=1;
        dfs(i);
    }
}
int main()
{
    std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int n,m;
    cin>>n>>m;
    edge.resize(n+1);
    for (int i=1;i<=m;i++)
    {
        int x,y;
        cin>>x>>y;
        edge[y].push_back(x);//反向建边
    }
    dfs(1);
    if(!edge[1].size())//看1有无边
    {
        vis[1]=1;
    }
    for (int i=1;i<=n;i++)
    {
        cout<<vis[i];
    }
    return 0;
}