欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Hihocoder 1870 Jin Yong’s Wukong Ranking List(DFS暴力签到)

程序员文章站 2022-05-20 20:51:45
...

Hihocoder 1870 Jin Yong’s Wukong Ranking List(DFS暴力签到)

题意

金庸写了很多武侠小说,粉丝们就在吵吵谁的武功高,给定n个判断武功水平高低(排在前面的比排在后面的人武功更高)的句子,找出最先出现冲突的一句输出。

思路

很简单的一个dfs水题,速切那种,结果我居然wa了四五发?

需要建立一个字符串到数字节点编号的映射(用map就行)

需要用DFS来判断会不会形成一个环(即强者弱者冲突)

其实本质就是一个拓扑排序的过程

因为N只有20个,所以随便暴力,我每个点都能当起点DFS找环。

具体我是这么做的:

  1. 建图的时候判断两个节点是否都已经存在于map内了,如果都已经存在了,标记该边为可能出现冲突的备选节点。因为两个节点如果有一个是新出现的节点就不可能发生冲突。
  2. 按加边的顺序遍历每一个已经被标记的边,把边加回到图中去,并进行DFS,如果出现了环则停止遍历,立即输出该条边,因为该边是第一个冲突的。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
unordered_map<string,int> maps;
struct edge
{
    string from;
    string sto;
    int fr;
    int to;
    int nxt;
    edge(string f,string tt,int fro,int t,int n):from(f),sto(tt),fr(fro),to(t),nxt(n){}
};
int egs[50];
vector<edge> edges;
bool edgegood[50];
void addedge(int f,int t,string fr,string to)
{
    edges.emplace_back(fr,to,f,t,egs[f]);
    egs[f]=edges.size()-1;
}//上面都是链式前向星的板子,因为本题需要用到加入边的序号
bool vis[50];
bool dfs(int num)
{
    if(vis[num])
    {
        return false;//访问过了,那就是有环
    }
    vis[num]=true;
    for(int i=egs[num];i!=-1;i=edges[i].nxt)
    {
        if(!edgegood[i])//还没加回的边先跳过,不通过它dfs
        {
            continue;
        }
        if(!dfs(edges[i].to))
        {
            return false;
        }

    }
    vis[num]=false;//一定要注意这里,wa了很冤的,如果有个Y字形的图不加这个就会出错。
    return true;
}
void solve(int n){
    edges.clear();
    memset(egs,-1,sizeof egs);
    maps.clear();
    int p=0;
    vector<int> qq;
    memset(edgegood,1,sizeof edgegood);//初始每条边都能通过
    for(int i=0;i<n;i++)
    {
        string a,b;
        cin>>a>>b;
        bool f1=true,f2=true;
        if(maps.find(a)==maps.end())
        {
            f1=false;
            maps[a]=++p;
        }
        if(maps.find(b)==maps.end())
        {
            f2=false;
            maps[b]=++p;
        }//新出现的节点分配一个编号
        int f = maps[a];
        int t = maps[b];
        addedge(f,t,a,b);
        if(f1 && f2)
        {
            edgegood[edges.size()-1]=false;//标记为暂时不能通过
            qq.push_back(edges.size()-1);//标记为待检查节点
        }
    }
    for(auto it: qq)
    {
        edgegood[it]=true;//把当前边加回到原图中去
        for(int i=1;i<=p;i++)
        {
            memset(vis,0,sizeof vis);
            if(!dfs(i))
            {
                cout<<edges[it].from<<" "<<edges[it].sto<<endl;
                return;
            }
        }
    }
    cout<<0<<endl;

}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    while (cin>>n)
        solve(n);
    return 0;
}

自己想出来的,感谢队友大力支持。

相关标签: DFS