大佬们,帮忙看看染色法为什么第七个点WA了,其他点都AC
  • 板块P1551 亲戚
  • 楼主抱山之石
  • 当前回复1
  • 已保存回复1
  • 发布时间2021/9/1 10:38
  • 上次更新2023/11/4 08:12:38
查看原帖
大佬们,帮忙看看染色法为什么第七个点WA了,其他点都AC
205665
抱山之石楼主2021/9/1 10:38
#include <iostream>
#include <list>
#include <vector>
using namespace std;
int main(){
    int n,m,p;
    int id=1;
    cin>>n>>m>>p;
    vector<int> arr(n+1,-1);//开一个人数+1的数组,这个数组从1开始,arr【i】的值代表第i个人的颜色,初始值为-1
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        /**两个人的关系体现在数组上只有这几种情况
         * 1.如果arr【a】和arr【b】的值都为-1,说明他们还没有和任何人有关系,处理方法是给他们赋予相同的颜色
         * 2.arr【a】为-1,arr【b】的值不为-1, 说明a没有和任何人有关系,处理方法是把b的颜色给a
         * 3.arr【b】为-1,arr【a】的值不为-1, 说明b没有和任何人有关系,处理方法是把a的颜色给b
         * 4.arr[a]和arr[b]的值都不为-1,说明a和b之前具有独立的亲属关系,处理方法是遍历整个数组,将所有值为arr[b]的元素替换为arr[a]
         **/
        if(arr[a]==arr[b] and arr[a]==-1){
//            arr[a]=arr[b]==id++;
            arr[a]=id;
            arr[b]=id;
            id++;
        }
        else if(arr[a]==-1 and arr[b]!=-1){
            arr[a]=arr[b];
        }
        else if(arr[a]!=-1 and arr[b]==-1){
            arr[b]=arr[a];
        }
        else if(arr[a]!=arr[b]){
            int t=arr[b];
            for(int j=1;j<=n;j++){
                if(arr[j]==t){
                    arr[j]=arr[a];
                }
            }
        }
    }
    for(int i=0;i<p;i++){
        int a,b;
        cin>>a>>b;
        /**判断的逻辑:
         * 1.如果两个值任意一个为-1,那么他们绝对没有亲属关系
         * 2.如果a不等于b,那么没有亲属关系
         * 3.如果a等于b,那么他们有亲属关系
         */
        if(arr[a]==-1||arr[b]==-1){
            cout<<"No"<<'\n';
        }
        else if(arr[a]!=arr[b]){
            cout<<"No"<<'\n';

        }
        else{
            cout<<"Yes"<<'\n';
        }
    }
    return 0;
}
2021/9/1 10:38
加载中...