【C++】数据结构之DFS

• • DFS
• 1.愿天下有情人都是失散多年的兄妹
• • 2.红色警报
  • 3.功夫传人

呵呵。大家都知道五服以内不得通婚，即两个人最近的共同祖先如果在五代以内（即本人、父母、祖父母、曾祖父母、高祖父母）则不可通婚。本题就请你帮助一对有情人判断一下，他们究竟是否可以成婚？

输入格式：

输入第一行给出一个正整数N（2 ≤ N ≤104），随后N行，每行按以下格式给出一个人的信息：

本人ID 性别 父亲ID 母亲ID

其中ID是5位数字，每人不同；性别M代表男性、F代表女性。如果某人的父亲或母亲已经不可考，则相应的ID位置上标记为-1。

接下来给出一个正整数K，随后K行，每行给出一对有情人的ID，其间以空格分隔。

注意：题目保证两个人是同辈，每人只有一个性别，并且血缘关系网中没有乱伦或隔辈成婚的情况。

输出格式：

对每一对有情人，判断他们的关系是否可以通婚：如果两人是同性，输出Never Mind；如果是异性并且关系出了五服，输出Yes；如果异性关系未出五服，输出No。

输入样例:

24
00001 M 01111 -1
00002 F 02222 03333
00003 M 02222 03333
00004 F 04444 03333
00005 M 04444 05555
00006 F 04444 05555
00007 F 06666 07777
00008 M 06666 07777
00009 M 00001 00002
00010 M 00003 00006
00011 F 00005 00007
00012 F 00008 08888
00013 F 00009 00011
00014 M 00010 09999
00015 M 00010 09999
00016 M 10000 00012
00017 F -1 00012
00018 F 11000 00013
00019 F 11100 00018
00020 F 00015 11110
00021 M 11100 00020
00022 M 00016 -1
00023 M 10012 00017
00024 M 00022 10013
9
00021 00024
00019 00024
00011 00012
00022 00018
00001 00004
00013 00016
00017 00015
00019 00021
00010 00011

输出样例：

Never Mind
Yes
Never Mind
No
Yes
No
Yes
No
No

AC代码

#include
using namespace std;
const int N=100010;
int vis[N];//标记路径
int flag;//标记
char sex[N];//判断性别
vectorV[N];//建立邻接矩阵储存图
void dfs(int id,int cnt)//深度搜索
{
    if(cnt==4) return;
    for(int i=0;i
        if(!vis[V[id][i]])
        {
            vis[V[id][i]]=1;
            dfs(V[id][i],cnt+1);
        }
        else 
        {
            flag=1;
            return;
        }
    }
}
int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        int id,fid,mid;
        char op;
        cin>>id>>op>>fid>>mid;
        sex[id]=op;
        if(fid!=-1)
        {
            sex[fid]='M';
            V[id].push_back(fid);
        }
        if(mid!=-1)
        {
            sex[mid]='F';
            V[id].push_back(mid);
        }
    }
    int k;
    cin>>k;
    while(k--)
    {
        int x,y;
        cin>>x>>y;
        if(sex[x]==sex[y]) {cout<<"Never Mind"< 
2.红色警报 
战争中保持各个城市间的连通性非常重要。本题要求你编写一个报警程序，当失去一个城市导致国家被分裂为多个无法连通的区域时，就发出红色警报。注意：若该国本来就不完全连通，是分裂的k个区域，而失去一个城市并不改变其他城市之间的连通性，则不要发出警报。
 
输入格式：
 
输入在第一行给出两个整数N（0 < N ≤ 500）和M（≤ 5000），分别为城市个数（于是默认城市从0到N-1编号）和连接两城市的通路条数。随后M行，每行给出一条通路所连接的两个城市的编号，其间以1个空格分隔。在城市信息之后给出被攻占的信息，即一个正整数K和随后的K个被攻占的城市的编号。
 
注意：输入保证给出的被攻占的城市编号都是合法的且无重复，但并不保证给出的通路没有重复。
 
输出格式：
 
对每个被攻占的城市，如果它会改变整个国家的连通性，则输出Red Alert: City k is lost!，其中k是该城市的编号；否则只输出City k is lost.即可。如果该国失去了最后一个城市，则增加一行输出Game Over.。
 
输入样例：
 
 
 
5 4
 0 1
 1 3
 3 0
 0 4
 5
 1 2 0 4 3
 
 
输出样例：
 
 
 
City 1 is lost.
 City 2 is lost.
 Red Alert: City 0 is lost!
 City 4 is lost.
 City 3 is lost.
 Game Over.
 
 
AC代码
 
#include
using namespace std;
const int N=505;
int g[N][N];
int vis[N];//存路径
int n,m;
int cnt1,cnt2;
void dfs(int x)
{
    for(int i=0;i
        if(vis[i]==0 and g[x][i]==1)
        {
            vis[i]=1;
            dfs(i);
        }
    }
    return ;
}
int main()
{
    cin>>n>>m;
    while(m--)
    {
        int a,b;
        cin>>a>>b;
        g[a][b]=g[b][a]=1;//合并并标记
    }
    memset(vis,0,sizeof vis);
    for(int i=0;i
        if(vis[i]==0)
        {
            dfs(i);
            cnt1++;//统计连通块的数量
        }
    }
    int k;
    cin>>k;
    for(int i=0;i
        int x;
        cnt2=0;
        memset(vis,0,sizeof vis);
        cin>>x;
        for(int j=0;j
            if(vis[j]==0)
            {
                dfs(j);
                cnt2++;
            }
        }
        if(cnt2>cnt1+1) printf("Red Alert: City %d is lost!n",x);
        else printf("City %d is lost.n",x);
        cnt1=cnt2;//更新新的连通块数量
    }
    if(n==k) printf("Game Over.n");
    return 0;
}
 
3.功夫传人 
一门武功能否传承久远并被发扬光大，是要看缘分的。一般来说，师傅传授给徒弟的武功总要打个折扣，于是越往后传，弟子们的功夫就越弱…… 直到某一支的某一代突然出现一个天分特别高的弟子（或者是吃到了灵丹、挖到了特别的秘笈），会将功夫的威力一下子放大N倍 —— 我们称这种弟子为“得道者”。
 
这里我们来考察某一位祖师爷门下的徒子徒孙家谱：假设家谱中的每个人只有1位师傅（除了祖师爷没有师傅）；每位师傅可以带很多徒弟；并且假设辈分严格有序，即祖师爷这门武功的每个第i代传人只能在第i-1代传人中拜1个师傅。我们假设已知祖师爷的功力值为Z，每向下传承一代，就会减弱r%，除非某一代弟子得道。现给出师门谱系关系，要求你算出所有得道者的功力总值。
 
输入格式：
 
输入在第一行给出3个正整数，分别是：N（≤105）——整个师门的总人数（于是每个人从0到N−1编号，祖师爷的编号为0）；Z——祖师爷的功力值（不一定是整数，但起码是正数）；r ——每传一代功夫所打的折扣百分比值（不超过100的正数）。接下来有N行，第i行（i=0,⋯,N−1）描述编号为i的人所传的徒弟，格式为：
 
Ki​ ID[1] ID[2] ⋯ ID[Ki​]
 
其中Ki​是徒弟的个数，后面跟的是各位徒弟的编号，数字间以空格间隔。Ki​为零表示这是一位得道者，这时后面跟的一个数字表示其武功被放大的倍数。
 
输出格式：
 
在一行中输出所有得道者的功力总值，只保留其整数部分。题目保证输入和正确的输出都不超过1010。
 
输入样例：
 
 
 
10 18.0 1.00
 3 2 3 5
 1 9
 1 4
 1 7
 0 7
 2 6 1
 1 8
 0 9
 0 4
 0 3
 
 
输出样例：
 
 
 
404
 
 
AC代码
 
#include
using namespace std;
const int N=100010;
vectorv[N];
int k,x;
bool st[N];
int n;
double z,r;
double sum=0;
void dfs(int u,double z)
{
    if(st[u])
    {
        sum=sum+z*v[u][0];//出现得道者就把当前得道者能量算出来
        return ;
    }
    else
    {
        for(int i=0;i
    cin>>n>>z>>r;
    r=(100-r)/100;//当前直接处理一下能量减少后剩余能量
    for(int i=0;i
        cin>>k;
        if(k==0)
        {
            st[i]=true;//进行标记一下 当前位置出现了得道者
            cin>>x;
            v[i].push_back(x);
        }
        else
        {
            for(int j=0;j
                cin>>x;
                v[i].push_back(x);//没有出现得道者就相当于建树
            }
        }
    }
    dfs(0,z);//从祖师爷开始搜索
    cout<<(int)sum<