HDU 1181 變形課 深度優先搜索(DFS)簡單題

題意：給出很多個字符串，每個串表示該串的首字母代表的物體能轉變成尾字母代表的物體，問的是'b'物體能不能轉變成'm'物體．

思路：先找出所有以'b'為首字母的串，它們都作為起點，一直很後搜索(連接)，看能否找到'm'

[cpp] 
#include<iostream>  
#include<string>  
#include<cstring>  
#include<algorithm>  
#include<cstdio>  
#include<cmath>  
#include<cctype>  
#include<iomanip>  
#include<queue>  
 
using namespace std; 
const int maxn=100000; 
 
char st[maxn],et[maxn]; 
int vis[maxn],t; 
bool ok; 
 
void DFS(int x){ 
    if(et[x]=='m'){ 
        ok=true; return; 
    } 
    for(int i=0;i<t;++i){ 
        if(vis[i]||st[i]!=et[x])continue; 
        vis[i]=1; 
        DFS(i); 
        vis[i]=0; 
        if(ok)return; 
    } 
} 
 
int main() { 
    string s; 
    while(cin>>s){ 
        t=0; 
        while(s[0]!='0'){ 
            st[t]=s[0]; 
            et[t++]=s[s.size()-1]; 
            cin>>s; 
        } 
        memset(vis,0,sizeof(vis)); 
        ok=false; 
        for(int i=0;i<t;++i){ 
            if(st[i]!='b')continue; 
            vis[i]=1; 
            DFS(i); 
        } 
        if(ok)puts("Yes."); 
        else puts("No."); 
    } 
    return 0; 
} 

#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cctype>
#include<iomanip>
#include<queue>

using namespace std;
const int maxn=100000;

char st[maxn],et[maxn];
int vis[maxn],t;
bool ok;

void DFS(int x){
    if(et[x]=='m'){
        ok=true; return;
    }
    for(int i=0;i<t;++i){
        if(vis[i]||st[i]!=et[x])continue;
        vis[i]=1;
        DFS(i);
        vis[i]=0;
        if(ok)return;
    }
}

int main() {
    string s;
    while(cin>>s){
        t=0;
        while(s[0]!='0'){
            st[t]=s[0];
            et[t++]=s[s.size()-1];
            cin>>s;
        }
        memset(vis,0,sizeof(vis));
        ok=false;
        for(int i=0;i<t;++i){
            if(st[i]!='b')continue;
            vis[i]=1;
            DFS(i);
        }
        if(ok)puts("Yes.");
        else puts("No.");
    }
    return 0;
}