数据分割

小w来到百度之星的赛场上，准备开始实现一个程序自动分析系统。

这个程序接受一些形如x_i = x_jxi=xj 或 x_i \neq x_jxi≠xj 的相等/不等约束条件作为输入，判定是否可以通过给每个 w 赋适当的值，来满足这些条件。

输入包含多组数据。然而粗心的小w不幸地把每组数据之间的分隔符删掉了。他只知道每组数据都是不可满足的，且若把每组数据的最后一个约束条件去掉，则该组数据是可满足的。

请帮助他恢复这些分隔符。

Input

第11行：一个数字LL，表示后面输入的总行数。

之后LL行，每行包含三个整数，i,j,ei,j,e，描述一个相等/不等的约束条件，若e=1e=1，则该约束条件为x_i = x_jxi=xj ，若e=0e=0，则该约束条件为 x_i \neq x_jxi≠xj 。

i,j,L \leq 100000i,j,L≤100000

x_i , x_j \leq Lxi,xj≤L

Output

输出共T+1T+1行。

第一行一个整数TT，表示数据组数。

接下来TT行的第ii行，一个整数，表示第i组数据中的约束条件个数。

Sample Input

Sample Output

1

6
———————————————————————————————————————
因为相等具有传递性所以我们可以用并查集维护一波
但是不等于不具有传递性所以我们可以用平衡树维护一波
当然这里我用的是set
这样之后呢 等于我们就可以把他们扔在一个并查集里面
不等于的就把不等于他的扔进他的平衡树里面
每次询问
如果是一对相等的数
我们就找一波他们是否在同一个并查集里 是就直接继续下一波
不是就找他们是否存在对方的平衡树里面 当然这里我们强行把size小的合并进大的里面保证复杂度
如果是不相等就判断他们是否同属一个并查集
是就清空一波 记录答案
不然就把他们加入对方的平衡树里面

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<set>

using namespace std;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int T,f[];

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

set<int>tr[];

int vis[],cnt=;

int ans[],ap;

int stk[],stp;

int a,b,h;

void clear(){

    while(stp){

        int x=stk[--stp];

        tr[x].clear();

        f[x]=x;

    }

    ++cnt;

}

int main()

{

    T=read();

    for(int i=;i<=;i++) f[i]=i;

    for(int i=;i<=T;i++){

        a=read(); b=read(); h=read();

        if(vis[a]!=cnt) stk[stp++]=a,vis[a]=cnt;

        if(vis[b]!=cnt) stk[stp++]=b,vis[b]=cnt;

        int p=find(a),q=find(b);

        if(tr[p].size()<tr[q].size()) swap(p,q);

        if(h==){

            if(p==q) continue;

            if(tr[p].find(q)!=tr[p].end()){

                clear();

                ans[++ap]=i;

                continue;

            }

            f[q]=p;

            for(set<int>::iterator it=tr[q].begin();it!=tr[q].end();it++){

                int z=*it;

                tr[z].erase(q);

                tr[z].insert(p);

                tr[p].insert(z);

            }

            tr[q].clear();

        }

        else{

            if(p==q){

                clear();

                ans[++ap]=i;

                continue;

            }

            tr[p].insert(q);

            tr[q].insert(p);

        }

    }

    printf("%d\n",ap);

    for(int i=;i<=ap;i++) printf("%d\n",ans[i]-ans[i-]);

    return ;

}

巴特西

百度之星初赛（A）——T2

数据分割

最新文章

热门文章