已AC,但不知道为什么在程序运行完后卡了一会
查看原帖
已AC,但不知道为什么在程序运行完后卡了一会
12755
星河·莫楼主2021/3/5 13:55

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdio>
using namespace std;
struct data_edge
{
	int a,b,yes_or_no;
}sn[1000000+5];
bool cmp(data_edge a,data_edge b)
{
	return a.yes_or_no>b.yes_or_no;
}
int ans_p,gs_a,t;
struct data
{
	struct hash
	{
		struct data1
		{
			int x,c;
		};
		int n;
		vector <data1> hash[1000007];
		int find_it(int x)//寻找有无重复 
		{
			int y=x%1000007;//求出目标的哈希值 
			if (hash[y].size()>0)
			{
				for (int i=0;i<=hash[y].size()-1;i++)
				if (hash[y][i].x==x) return hash[y][i].c;//寻找有无重复
			}
			return -1;
		}
		void add(int num)//入队 
		{
			int p=find_it(num);//寻找有无重复
			
			if (p==-1)
			{
				int y=num%1000007;
				
				n++;
				data1 fff;
				fff.x=num;
				fff.c=n;
				hash[y].push_back(fff);//如果无,入队 
				p=n;
			}
		}
	};
	hash has;
	struct bcj
	{
	    int s[2000000+5],cz,cs1,cs2,n,m;
	    int cxg(int p)
	    {
	        int zz=p;
	        while (s[zz]>=0)
	        zz=s[zz];
	        int zz2=p;
	        while (zz!=p)
	        {zz2=s[p];s[p]=zz;p=zz2;}
	        return zz;
	    }//找其祖先 
	    void hb(int hb1,int hb2)
	    {
	        int zz1=cxg(hb1);
	        int zz2=cxg(hb2);
	        if (zz1!=zz2)
	        if (s[zz1]<s[zz2])
	        {
		        s[zz1]+=s[zz2];
		        s[zz2]=zz1;
	        }
	        else
	        {
		        s[zz2]+=s[zz1];
		        s[zz1]=zz2;
	        }
	        return ;
	    }//合并两个祖先 
	    bool cxqq(int p1,int p2)
	    {
	        if (cxg(p2)==cxg(p1))
	        return 1;
	        else
	        return 0;
	    }//判断两个人是否在同一个集合中
	}bc;
	void get_data()
	{
	    ans_p=1;
	    bc.n=has.n;
	    for (int i=1;i<=bc.n;i++)
	    bc.s[i]=-1;
	    for (int i=1;i<=gs_a;i++)
	    {
		    if (sn[i].yes_or_no==1)
		    bc.hb(has.find_it(sn[i].a),has.find_it(sn[i].b));
		    else
		    if (bc.cxqq(has.find_it(sn[i].a),has.find_it(sn[i].b))==1) ans_p=0;
	    }
	}
}data_use[10+5];
int main()
{
	scanf("%d",&t);
	for (int test=1;test<=t;test++)
	{
		scanf("%d",&gs_a);
		//cout<<"A"<<endl;
		for (int i=1;i<=gs_a;i++)
		scanf("%d%d%d",&sn[i].a,&sn[i].b,&sn[i].yes_or_no);
		//cout<<"B"<<endl;
		sort(sn+1,sn+gs_a+1,cmp);
		//cout<<"C"<<endl;
		for (int i=1;i<=gs_a;i++)
		{
			data_use[test].has.add(sn[i].a);
			data_use[test].has.add(sn[i].b);
		}		
		//cout<<"D"<<endl;
		data_use[test].get_data();
		//cout<<"E"<<endl;
		if (ans_p==0) printf("NO\n"); else printf("YES\n");
		//cout<<"End "<<test<<endl;
	}
	//cout<<"Finish"<<endl;
	return 0;
}

2021/3/5 13:55
加载中...