[图片上传中...(L2-010(2).png-6adbc7-1553435350204-0)]

L2-010(2).png

分析

这道题就是一道找朋友的朋友的题目
一看到这个题目首先我想到的是dfs，不过在用dfs写的过程中报错了一个点，目前还没想通原因
后来想想，找朋友的朋友这种题目肯定用并查集更加方便呀！所以又撸了一个并查集的版本，无脑通过~

ac代码（并查集）

#include<bits/stdc++.h>
using namespace std;
int mp[101][101]={0};
int f[101];

int find(int x){
    return f[x]==x?x:f[x]=find(f[x]);
}

void merge(int a,int b){
    int x=find(a);
    int y=find(b);
    if(x!=y){
        f[y]=x;
    }
}

int main(){
    for(int i=1;i<101;i++){
        f[i]=i;
    }
    int n,m,k;
    cin>>n>>m>>k;
    for(int i=0;i<m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        mp[a][b]=mp[b][a]=c;
        if(c==1){
            merge(a,b); 
        }
    }
    
    for(int i=0;i<k;i++){
        int a,b;
        cin>>a>>b;
        
        int flag=0;
        if(find(a)==find(b)){
            flag=1;
        }
        
        if(flag==1 && mp[a][b]!=-1){
            cout<<"No problem"<<endl;
        }else if(flag==0 && mp[a][b]==0){
            cout<<"OK"<<endl;
        }else if(flag==1 && mp[a][b]==-1){
            cout<<"OK but..."<<endl;
        }else{
            cout<<"No way"<<endl;
        }
    }
}

ac代码（DFS）

#include<bits/stdc++.h>
using namespace std;

int mp[101][101]={0};
int n;
int visit[101]={0};




bool dfs(int a,int b){
    if(a==b){
        return true;
    }
    if(visit[a]==1){
        return false;
    }
    visit[a]=1;
    for(int i=1;i<=n;i++){
        if(mp[a][i]==1 && dfs(i,b)==true)
            return true;
    }
    return false;
}


int main(){
    int m,k;
    cin>>n>>m>>k;
    for(int i=0;i<m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        mp[a][b]=mp[b][a]=c;
    }
    
    for(int i=0;i<k;i++){
        int a,b;
        for(int j=1;j<=n;j++){
            visit[j]=0;
        }
        cin>>a>>b;
        int flag=dfs(a,b);
        if(flag==1 && mp[a][b]!=-1){
            cout<<"No problem"<<endl;
        }else if(flag==0 && mp[a][b]==0){
            cout<<"OK"<<endl;
        }else if(flag==1 && mp[a][b]==-1){
            cout<<"OK but..."<<endl;
        }else{
            cout<<"No way"<<endl;
        }
    }
}

ac代码（未能通过的dfs，还没想清楚原因）

#include<bits/stdc++.h>
using namespace std;

int mp[101][101]={0};
int n;int flag=0;
int visit[101]={0};


void dfs(int n,int d){
    visit[n]=1;
    if(mp[n][d]==1){
        flag=1;
        return;
    }
    for(int i=1;i<=n;i++){
        if(visit[i]==0 && mp[n][i]==1){
            visit[i]=1;
            dfs(i,d);
        }
    }
}

int main(){
    int m,k;
    cin>>n>>m>>k;
    for(int i=0;i<m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        mp[a][b]=mp[b][a]=c;
    }
    
    for(int i=0;i<k;i++){
        int a,b;
        flag=0;
        for(int j=1;j<=n;j++){
            visit[j]=0;
        }
        cin>>a>>b;
        dfs(a,b);
        if(flag==1 && mp[a][b]!=-1){
            cout<<"No problem"<<endl;
        }else if(flag==0 && mp[a][b]==0){
            cout<<"OK"<<endl;
        }else if(flag==1 && mp[a][b]==-1){
            cout<<"OK but..."<<endl;
        }else{
            cout<<"No way"<<endl;
        }
    }
}