2024SMUSpring天梯2补题

L2-2:红色警报

题意:

只要连通块数目减少就输出RedAlert,主要是连通块数目..

int n,m,k;
unordered_map<int,int> mark;
vector<int> vct[505];
bool vis[505];
void dfs(int x){
    for(auto v:vct[x]){
        if(!vis[v]&&!mark[v]){
            vis[v]=1;
            dfs(v);
        }
    }
}
void solve(){                   //L2-2      ??---
    // 题意理解错了,不是现有国家整体从连通到不连通才输出RedAlert。而是只要国家连通块增加了，就输出RedAlert..
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        vct[u].emplace_back(v);
        vct[v].emplace_back(u);
    }
    cin>>k;
    int cntBlock=0;
    for(int i=0;i<n;i++) {
        if(!vis[i]){
            vis[i]=1;
            dfs(i);
            cntBlock++;
        }
    }
    for(int i=1;i<=k;i++){
        int bd; cin>>bd;
        mark[bd]=1;
        memset(vis,0,sizeof(vis));
        int curcnt=0;
        for(int j=0;j<n;j++){
            if(!vis[j]&&!mark[j]){
                dfs(j);
                vis[j]=1;
                curcnt++;
            }
        }
        if(curcnt<=cntBlock) cout<<"City "<<bd<<" is lost."<<endl;
        else cout<<"Red Alert: City "<<bd<<" is lost!"<<endl;
        cntBlock=curcnt;
    }
    if(k==n) cout<<"Game Over.";
}

L2-3:排座位

题意:

朋友关系可以传递，敌对关系不可以传递。

int fa[300];//1-100存朋友关系.101-200存敌对关系.---no！！敌对关系不会传递！！
int find(int x){
    if(x!=fa[x]) fa[x]=find(fa[x]);
    return fa[x];
}
void Union(int x,int y){
    int fa1=find(x),fa2=find(y);
    fa[fa1]=fa2;
}
void solve(){                       //L2-3
    //要用并查集，用map写的话只有22分，扣3分。。因为长的传递关系map识别不出来..
    int n,m,k;
    cin>>n>>m>>k;
    for(int i=1;i<=100;i++) fa[i]=i;
    unordered_set<int> hate[105];
    for(int i=1;i<=m;i++){
        int u,v,rela;
        cin>>u>>v>>rela;
        if(rela==-1){
            hate[u].insert(v);   //一个人敌对的人可能有多个
            hate[v].insert(u);
        }
        else if(find(u)!=find(v)) Union(u,v);
    }
    while(k--){
        int u,v; cin>>u>>v;
        int frdu=find(u),frdv=find(v);
        if((hate[u].find(v)!=hate[u].end())&&frdu==frdv) cout<<"OK but..."<<endl;
        else if(hate[u].find(v)!=hate[u].end()) cout<<"No way"<<endl;
        else if(frdu==frdv) cout<<"No problem"<<endl;
        else cout<<"OK"<<endl;
    }
}