题解：CF164A Variable, or There and Back Again

· · 题解

CF164A 题解

题目传送门

蒟蒻的第一篇题解，求过！！！

题目大意

说实话，其实下面两位大佬写的题目大意已经够详细了。不过要注意的是，可能存在多个标记为 1 和 2 的点，从标号为 1 到标号 2 的路径可能不止一条，并且题目要求的是所有可以从标号为 1 到标号 2 的路径所经过的点有哪些。

暴力做法

思路

暴力的算法应该不难想出来，只需要遍历所有标记为 1 的点，然后一个一个点往后找，找到标记为 2 点就更新一下被标记过的点。

代码

这个代码还可以优化。

#include<bits/stdc++.h>
using namespace std;
int n,m,f[100010],r[100010],maxn=0,ansr[100010];
vector<int> ve[100010];
void get_ans(){//标记 
    for(int i=1;i<=n;i++){
        ansr[i]=max(r[i],ansr[i]);
    }
}
void dfs(int d,int maxl){//深度优先搜索 
    if(r[d]==1) return; //已经被遍历过了 
    r[d]=1;//标记走过 
    if(f[d]==2){
        get_ans();
    }
    for(int i=0;i<ve[d].size();i++){
        dfs(ve[d][i],maxl+1);
    }
    r[d]=0;//回溯 
}
void add(int x,int y){//存边，注意是有向图 
    ve[x].push_back(y);
    //ve[y].push_back(x);
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&f[i]);
    }
    for(int i=1;i<=m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y);
    }
    for(int i=1;i<=n;i++){
        if(f[i]==1){
            dfs(i,1);
        }
    }
    for(int i=1;i<=n;i++){
        printf("%d\n",ansr[i]);
    }
    return 0;
}

满分做法

思路

其实我们只需要换一个思路。可以从所有标记为 1 的点开始遍历存下可以达到的点有哪些，从标记为 2 的点开始遍历也存下可以达到的点有哪些，如果一个点同时被标记了两次，那么说明这个点可以被访问过。

这里也有一个注意点，就是应该注意在第二次遍历的时候，碰到标记为 1 的点就应该标记后并结束，而不是继续遍历下去（因为这个我 WA 了两次）。

代码

代码我是使用 DFS 实现的，楼下两个大佬都是 BFS。

我才不会告诉你我是因为 BFS 不会才用 DFS 的。

#include<bits/stdc++.h>
using namespace std;
int n,m,f[100010],r[100010],maxn=0,k1[100010],k2[100010];
vector<int> ve1[100010],ve2[100010];
void add(int x,int y){
    ve1[x].push_back(y);
    ve2[y].push_back(x);
}
void dfs1(int d){//标记为1的遍历 
    if(k1[d]) return;
    k1[d]=1;
    for(int i=0;i<ve1[d].size();i++){
        dfs1(ve1[d][i]);
    }
}
void dfs2(int d){//标记为2的遍历 
    if(k2[d]) return;
    k2[d]=1;
    if(f[d]==1) return;//遇到标记为1的就应该标记后就停止遍历 
    for(int i=0;i<ve2[d].size();i++){
        dfs2(ve2[d][i]);
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&f[i]);
    }
    for(int i=1;i<=m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y);
    }
    for(int i=1;i<=n;i++){
        if(f[i]==1){//遇到标记为1的 
            dfs1(i);
        }else if(f[i]==2){//遇到标记为2的 
            dfs2(i);
        }
    }
    for(int i=1;i<=n;i++){
        if(k1[i]+k2[i]==2) printf("1\n");
        else printf("0\n");
    }
    return 0;
}