[題解]51nod_1515_明辨是非

好久沒有話多了，是覺得有點浪費時間，今天考試和一中用的一樣的題，結果反而考得不好，不過Jackpei一句知恥而後勇點醒夢中人偷偷@Jackpei

就是這樣吧

還有我極度懷疑我的鍵帽打油了......我買了假的PBT還是我的手實在是太油了......

強制在線，因為不等關係沒有傳遞性，於是用set維護不等關係，并查集維護相等關係，

合併時把set也合併掉，具體就是直接複製合併，複雜度可以接受，雖然並不會算

於是大力瞎搞，我調了半天錯在了合併set搞錯了，it本來就是s[xx]的迭代器，怎麼能和自己互相插入呢......

#include<bits/stdc++.h>

using namespace std;

const int maxn=;//開兩倍

int n,cnt=;

int fa[maxn];

set<int>s[maxn];

map<int,int>m;

int find(int x)

{

    while(x!=fa[x])x=fa[x]=fa[fa[x]];

    return x;

}

int main()

{

    scanf("%d",&n);

    for(int i=;i<=n*;i++)fa[i]=i;

    for(int i=,x,y,p;i<=n;i++){

        scanf("%d%d%d",&x,&y,&p);

        if(m[x])x=m[x];

        else x=m[x]=++cnt;

        if(m[y])y=m[y];

        else y=m[y]=++cnt;

        int xx=find(x),yy=find(y);

        if(p==){

            if(s[xx].count(yy))puts("NO");

            else if(xx!=yy){

                puts("YES");

                if(s[xx].size()>s[yy].size())swap(xx,yy);

                fa[xx]=yy;

                for(set<int>::iterator it=s[xx].begin();it!=s[xx].end();it++)

                s[*it].insert(yy),s[yy].insert(*it);

            }

            else puts("YES");

        }

        else{

            if(xx==yy)puts("NO");

            else{

                s[xx].insert(yy);s[yy].insert(xx);

                puts("YES");

            }

        }

    }

}

巴特西

[題解]51nod_1515_明辨是非

最新文章

热门文章