[CCCC]7-39 红色警报 （25 分)- DFS

7-39.png

分析

考察dfs，不过这道题有个大坑点。。。因为一次警报要遍历两次图，通过前后的对比才能得知是否是红色警报。。。应该要做两次清零
用二维数组做的时候能通过全部测试点，但是用向量数组做的时候有几个点就是过不了，不知道是哪里的问题，至今未解决。。。

ac代码

#include<iostream>
using namespace std;

int N,M;
int map[505][505]={0};
int book[505]={0};
int gongzhan[505]={0};

void dfs(int city){
    book[city]=1;
    for(int i=0;i<N;i++){
        if(!book[i] && map[city][i]==1 && !gongzhan[city]){
            book[i]=1;
            dfs(i);
        }
    }
}

int num(){
    int count=0;
    for(int i=0;i<N;i++){
        if(book[i]==0 && gongzhan[i]==0){
            dfs(i);
            count++;
        }
    }
    return count;
}

int main(){
    cin>>N>>M;
    for(int i=0;i<M;i++){
        int a,b;
        cin>>a>>b;
        map[a][b]=map[b][a]=1;
    }
    int K;
    cin>>K;
    for(int i=0;i<K;i++){
        int city;
        cin>>city;
        
        for(int i=0;i<N;i++){
            book[i]=0;
        }
        int pre=num();
        
        gongzhan[city]=1;
        
        for(int i=0;i<N;i++){
            book[i]=0;
        }
        int after=num();
        if(after>pre){
            printf("Red Alert: City %d is lost!\n",city);
        }else{
            printf("City %d is lost.\n",city);
        }
        
        //game over结束标志
        int flag=0;
        for(int j=0;j<N;j++){
            if(gongzhan[j]==0){
                flag=1;
            }
        }
        if(flag==0){
            cout<<"Game Over."<<endl;
            break;
        }
    }
}

向量数组做法（没能ac）

#include<bits/stdc++.h>
using namespace std;
int n,m;
vector<int> mp[500];
int visit[500];
int gongzhan[500];


void dfs(int i){
    visit[i]==1;
    for(int j=0;j<mp[i].size();j++){
        if(gongzhan[mp[i][j]]==0 && visit[mp[i][j]]==0 ){
            visit[mp[i][j]]=1;
            dfs(mp[i][j]);
        }
    }
}

int num(){
    int number=0;
    for(int i=0;i<n;i++){
        if(gongzhan[i]==0 && visit[i]==0){
            dfs(i);
            number++;
        }
    }
    return number;
}


int main(){
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        mp[a].push_back(b);
        mp[b].push_back(a);
    }
    /*
    for(int i=0;i<n;i++){
        for(int j=0;j<mp[i].size();j++){
            cout<<mp[i][j]<<" ";
        }
        cout<<endl;
    }
    */
    
    int k;
    cin>>k;
    for(int i=0;i<k;i++){
        int city;
        cin>>city;
        
        for(int j=0;j<n;j++){
            visit[j]=0;
        }
        int pre=num();
        
        gongzhan[city]=1;
        
        for(int j=0;j<n;j++){
            visit[j]=0;
        }
        int last=num();
        
        if(last>pre){
            printf("Red Alert:City %d is lost.\n",city);
        }else{
            printf("City %d is lost.\n",city);
        }
        
        int flag=0;
        for(int j=0;j<n;j++){
            if(gongzhan[j]==0){
                flag=1;
            }
        }
        if(flag==0){
            cout<<"Game Over."<<endl;
        }
        
    }
}