相关链接
题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=4195
解题报告
用并查集将相同的变量缩起来
然后判有没有两个不等的变量在一个连通分量即可
Code
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 200009;
const int M = 300009;
int n, fa[N], cet[M], val[N], dif[N];
inline int read() {
char c = getchar(); int ret = 0, f = 1;
for (; c < '0' || c > '9'; f = c == '-'? -1: 1, c = getchar());
for (; '0' <= c && c <= '9'; ret = ret * 10 + c - '0', c = getchar());
return ret * f;
}
inline int find(int x) {
return fa[x] == x? x: fa[x] = find(fa[x]);
}
int main() {
freopen("prog.in", "r", stdin);
freopen("prog.out", "w", stdout);
for (int T = read(); T; T--) {
n = read();
int tot = 0, cnt = 0, tt = 0;
for (int i = 1; i <= n; i++) {
cet[++tot] = val[++cnt] = read();
cet[++tot] = val[++cnt] = read();
cet[++tot] = read();
}
sort(val + 1, val + 1 + cnt);
cnt = unique(val + 1, val + 1 + cnt) - val - 1;
for (int i = 1; i <= cnt; i++) {
fa[i] = i;
}
for (int i = 1; i <= n; i++) {
int t = cet[tot--];
int u = cet[tot--], v = cet[tot--];
u = lower_bound(val + 1, val + 1 + cnt, u) - val;
v = lower_bound(val + 1, val + 1 + cnt, v) - val;
if (t == 1) {
fa[find(u)] = find(v);
} else {
dif[++tt] = u;
dif[++tt] = v;
}
}
bool ok = 1;
for (int i = 1; i <= tt; i += 2) {
int u = dif[i], v = dif[i + 1];
if (find(u) == find(v)) {
ok = 0;
break;
}
}
puts(ok? "YES": "NO");
}
return 0;
}
I seriously love your blog.. Excellent colors & theme.
Did you create this amazing site yourself? Please reply back as I’m hoping to
create my own blog and would like to know where you got
this from or what the theme is called. Appreciate it!
Good site you’ve got here.. It’s hard to find good quality writing like yours nowadays.
I honestly appreciate people like you! Take care!!
I love your blog.. very nice colors & theme. Did you make this website yourself or did you hire someone to do it for you?
Plz reply as I’m looking to design my own blog and would like to know where u got this
from. thank you
After looking into a handful of the articles on your web site,
I seriously like your technique of writing a blog. I saved
it to my bookmark website list and will be checking back in the near future.
Take a look at my web site as well and tell me
how you feel.
Hi this is somewhat of off topic but I was wanting to know
if blogs use WYSIWYG editors or if you have to
manually code with HTML. I’m starting a blog soon but have no coding experience so I wanted to get advice from someone with experience.
Any help would be enormously appreciated!
Hello my loved one! I wish to say that this post is amazing, great written and
come with almost all vital infos. I would like to look more
posts like this .
I truly love your website.. Very nice colors & theme.
Did you develop this site yourself? Please reply back as I’m trying to create my very own website and want to learn where you got this from or just what the theme is named.
Many thanks!
Hello there! Would you mind if I share your blog with my zynga group?
There’s a lot of folks that I think would really enjoy your content.
Please let me know. Thank you
Do you have any video of that? I’d love to find out some additional information.
Magnificent beat ! I would like to apprentice while you amend your site, how could i subscribe for a blog web site?
The account helped me a acceptable deal. I had been tiny bit acquainted of this your broadcast
offered bright clear idea
Wow! Finally I got a webpage from where I can truly obtain useful facts concerning my study and knowledge.
Unquestionably imagine that which you said. Your favourite reason appeared to be at the internet the simplest factor to take into
account of. I say to you, I certainly get irked at the same time as other folks
consider concerns that they plainly do not recognise about.
You controlled to hit the nail upon the highest and also outlined
out the whole thing without having side-effects , folks could take a
signal. Will likely be again to get more. Thank you
Hey there, You have done a fantastic job. I’ll definitely digg it
and personally suggest to my friends. I’m confident they will be
benefited from this website.
I would like to thank you for the efforts you have put in writing this
website. I am hoping to check out the same high-grade blog posts from you in the
future as well. In truth, your creative writing abilities has motivated me to get my
very own blog now 😉
Everyone loves it when individuals get together and share views.
Great blog, keep it up! natalielise pof
I love your blog.. very nice colors & theme. Did you design this
website yourself or did you hire someone to do it for you?
Plz answer back as I’m looking to create my own blog and would like to know where u got
this from. thanks
Good post. I learn something new and challenging on blogs
I stumbleupon everyday. It’s always interesting to read articles from
other authors and practice a little something from other websites.
This is really fascinating, You are an excessively professional
blogger. I’ve joined your rss feed and look ahead to in the
hunt for extra of your great post. Additionally, I’ve shared your website in my social networks
Your style is so unique in comparison to other folks I have read stuff from.
Many thanks for posting when you’ve got the opportunity, Guess I’ll just book mark this blog.
natalielise plenty of fish
Appreciation to my father who told me regarding
this blog, this blog is really remarkable.
This is a topic that’s close to my heart… Best wishes!
Where are your contact details though?
Hey there! I’ve been following your web site for a long time now and finally got the courage to
go ahead and give you a shout out from Lubbock Texas! Just wanted to tell you keep up the good work!
Oh my goodness! Impressive article dude! Many thanks,
However I am experiencing problems with your RSS. I don’t know the reason why I cannot join it.
Is there anybody getting identical RSS problems? Anyone that knows the answer can you kindly respond?
Thanx!!
Very descriptive blog, I enjoyed that bit.
Will there be a part 2? natalielise plenty of fish
If you would like to improve your knowledge just keep visiting this web site and be updated with the newest information posted here.
plenty of fish natalielise
Pretty! This was an extremely wonderful post.
Thank you for providing these details.
Hello very cool web site!! Guy .. Excellent .. Amazing ..
I will bookmark your site and take the feeds also? I’m happy to find so many helpful information right here within the post,
we’d like develop extra techniques on this regard, thanks for sharing.
. . . . .
Hello! Do you know if they make any plugins to assist with SEO?
I’m trying to get my blog to rank for some targeted keywords but I’m not
seeing very good success. If you know of any please share.
Thanks!
This is really interesting, You’re a very skilled blogger.
I have joined your feed and look forward to seeking more of your
great post. Also, I have shared your website in my
social networks!
It’s an amazing paragraph for all the online visitors; they will obtain benefit from it I am sure.
Hi there colleagues, how is all, and what you wish for to say regarding this paragraph, in my view its really amazing
in favor of me.
This site was… how do I say it? Relevant!! Finally I have found something which helped me.
Thanks a lot!
Right here is the perfect blog for anyone who really wants to understand this
topic. You know a whole lot its almost hard to argue with you (not that I actually would want to…HaHa).
You certainly put a new spin on a subject that has been written about for decades.
Wonderful stuff, just great!
excellent issues altogether, you simply won a logo new reader.
What would you recommend in regards to your publish that you just made a few days in the past?
Any certain?
Hello, I want to subscribe for this webpage
to get most up-to-date updates, thus where can i do it please help.
Whoa! This blog looks exactly like my old one!
It’s on a totally different topic but it has pretty much
the same page layout and design. Superb choice of colors!
Thank you for the auspicious writeup. It in fact was a amusement account
it. Look advanced to more added agreeable from you!
By the way, how can we communicate?
I used to be suggested this blog by way of my cousin. I
am no longer certain whether or not this publish is
written through him as nobody else recognise such distinct approximately my difficulty.
You are amazing! Thank you!
I appreciate, cause I found exactly what I was taking a look for.
You have ended my four day long hunt! God Bless you man.
Have a nice day. Bye
What’s up i am kavin, its my first time to commenting anywhere, when i read this
piece of writing i thought i could also create comment
due to this brilliant post.
Hello there, You have done an excellent job. I will certainly digg it
and personally suggest to my friends. I am sure they’ll be benefited from this web site.
Your style is unique compared to other folks I have read stuff from.
Thanks for posting when you have the opportunity, Guess I’ll
just book mark this site.
This is very interesting, You are an excessively professional blogger.
I have joined your rss feed and sit up for in the hunt for more of your great post.
Additionally, I have shared your web site in my social
networks
What’s up i am kavin, its my first time to commenting anyplace,
when i read this piece of writing i thought i could also create comment due
to this sensible piece of writing.
hey there and thank you for your info – I’ve definitely picked up something new from right here.
I did however expertise several technical points using this site,
as I experienced to reload the website many times
previous to I could get it to load correctly. I had been wondering if
your web hosting is OK? Not that I’m complaining, but
sluggish loading instances times will very frequently affect your placement in google and could damage your
high-quality score if advertising and marketing with Adwords.
Well I am adding this RSS to my email and can look out for a lot more of your
respective fascinating content. Make sure you update this again very soon.
Can I simply just say what a comfort to
find somebody who really understands what they’re discussing online.
You definitely understand how to bring an issue to light and make it important.
A lot more people ought to read this and understand this side
of the story. I was surprised that you’re not more
popular because you definitely have the gift.
I’m not sure where you’re getting your info, but good topic.
I needs to spend some time learning more or understanding more.
Thanks for excellent info I was looking for this information for my mission.
I was curious if you ever thought of changing the structure of your blog?
Its very well written; I love what youve got to say. But maybe
you could a little more in the way of content so people
could connect with it better. Youve got an awful lot of text for only
having 1 or 2 pictures. Maybe you could space it out better?
Superb, what a webpage it is! This weblog presents helpful data to us, keep it up.
Greetings! I know this is kinda off topic however , I’d figured I’d ask.
Would you be interested in trading links or maybe guest
authoring a blog post or vice-versa? My blog addresses a lot of the same
topics as yours and I believe we could greatly benefit from each other.
If you happen to be interested feel free to send me an email.
I look forward to hearing from you! Excellent blog by the way!
Hi, i believe that i saw you visited my website thus i came to return the choose?.I’m attempting to find issues to improve my web site!I assume its adequate to use a few of your ideas!!
Every weekend i used to visit this web site, as i want enjoyment, as this this
site conations genuinely pleasant funny material
too.
Heya i am for the first time here. I found this board and I find It truly useful & it helped me out a lot.
I hope to give something back and help others like you helped me.
Hello! I could have sworn I’ve been to this website before but after browsing through
many of the posts I realized it’s new to me. Anyhow, I’m certainly
delighted I came across it and I’ll be book-marking it and
checking back frequently!
If you would like to grow your familiarity just keep visiting this
web page and be updated with the hottest gossip posted here.
Definitely imagine that that you said. Your favorite justification seemed to be
on the net the easiest factor to take into accout of. I say to you, I certainly get irked while other people consider worries that they plainly do not recognise about.
You controlled to hit the nail upon the highest as smartly
as defined out the entire thing without having side-effects ,
people could take a signal. Will likely be again to
get more. Thanks
I all the time used to read piece of writing in news papers
but now as I am a user of web so from now I am using net
for articles, thanks to web.
Hello There. I discovered your weblog the usage of msn. This is an extremely
smartly written article. I’ll be sure to bookmark it and
return to read more of your helpful information. Thanks for
the post. I will certainly return.
Asking questions are truly nice thing if you are not understanding anything
entirely, except this article offers nice understanding yet.
Hello there! This is kind of off topic but I need some guidance from an established blog.
Is it tough to set up your own blog? I’m not very techincal
but I can figure things out pretty quick. I’m thinking about making my own but I’m
not sure where to begin. Do you have any tips or suggestions?
With thanks
Actually no matter if someone doesn’t understand afterward its
up to other people that they will assist, so here it occurs.
Hi there, i read your blog occasionally and i own a similar one and i was just wondering if you get
a lot of spam remarks? If so how do you protect against it,
any plugin or anything you can recommend? I get so
much lately it’s driving me mad so any assistance is very much
appreciated.
Howdy would you mind letting me know which hosting
company you’re using? I’ve loaded your blog in 3
different browsers and I must say this blog loads a lot faster then most.
Can you suggest a good web hosting provider at a reasonable price?
Cheers, I appreciate it!
It’s an amazing piece of writing for all the web visitors;
they will obtain benefit from it I am sure.
You actually make it seem so easy with your presentation but I find this matter to be actually
something that I think I would never understand. It seems too
complex and very broad for me. I am looking forward for your next post, I will try
to get the hang of it!
This article presents clear idea in favor of the new viewers
of blogging, that actually how to do blogging and site-building.
Appreciate this post. Will try it out.
Hello, Neat post. There’s an issue together with your website in internet explorer, could test this?
IE still is the market chief and a good portion of folks will leave out your wonderful
writing due to this problem.
Howdy! Someone in my Myspace group shared this website with
us so I came to look it over. I’m definitely enjoying the
information. I’m bookmarking and will be tweeting this to my followers!
Exceptional blog and great design.
This is very interesting, You are a very skilled blogger.
I have joined your rss feed and look forward to seeking more of your fantastic
post. Also, I’ve shared your web site in my social networks!
Write more, thats all I have to say. Literally, it seems as though you relied on the video to make your
point. You obviously know what youre talking about, why throw away your intelligence on just posting videos
to your blog when you could be giving us something informative to read?
Hi there! I could have sworn I’ve been to this blog before but after checking through some of the post I realized
it’s new to me. Anyhow, I’m definitely glad I found it and
I’ll be bookmarking and checking back often!
An impressive share! I have just forwarded this onto a friend who had been conducting a little research on this.
And he in fact ordered me dinner because I found it for him…
lol. So allow me to reword this…. Thank YOU for the meal!!
But yeah, thanx for spending the time to discuss this issue here on your
web page.
What’s up Dear, are you in fact visiting this web page on a regular
basis, if so then you will without doubt obtain nice experience.
I quite like looking through an article that will make people think.
Also, thanks for allowing me to comment!
As a Newbie, I am continuously exploring online for articles that can aid me. Thank you
My spouse and I stumbled over here different web address and
thought I might as well check things out. I like what
I see so i am just following you. Look forward to finding out about your web page again.
Hey there would you mind stating which blog platform
you’re working with? I’m going to start my own blog in the
near future but I’m having a difficult time selecting between BlogEngine/Wordpress/B2evolution and Drupal.
The reason I ask is because your layout seems different
then most blogs and I’m looking for something unique.
P.S Sorry for getting off-topic but I had to ask!
Hello there! This article couldn’t be written much better!
Looking through this article reminds me of my previous roommate!
He continually kept talking about this. I’ll forward this article to him.
Fairly certain he’ll have a great read. Thanks for sharing!
Everyone loves what you guys are up too. This kind of clever work
and coverage! Keep up the terrific works guys I’ve added you guys to blogroll.
It’s nearly impossible to find experienced
people for this subject, but you sound like you know what you’re talking about!
Thanks
Whats up this is kind of of off topic but I was wondering if blogs use WYSIWYG editors or if you have to manually code with HTML.
I’m starting a blog soon but have no coding expertise so I wanted to get advice from someone with experience.
Any help would be enormously appreciated!
I’m really enjoying the theme/design of your website.
Do you ever run into any browser compatibility issues?
A number of my blog visitors have complained about my site not working correctly in Explorer but looks great in Firefox.
Do you have any solutions to help fix this issue?
Does your website have a contact page? I’m having trouble locating it
but, I’d like to send you an e-mail. I’ve got
some suggestions for your blog you might be interested in hearing.
Either way, great blog and I look forward to seeing it grow over time.
Great post! We will be linking to this particularly great content on our website.
Keep up the great writing.
It’s truly very complicated in this active life to listen news on TV, so I just use
the web for that purpose, and get the newest news.
Aw, this was an exceptionally nice post.
Taking a few minutes and actual effort to make a superb article… but what can I say… I procrastinate a whole lot and don’t manage
to get anything done.
I think the admin of this web page is actually working hard in favor of his web site,
for the reason that here every information is quality based material.
Its not my first time to go to see this site,
i am visiting this website dailly and take pleasant facts from here
daily.
It’s remarkable to visit this web site and reading the views of all friends concerning this article, while I am also zealous of getting experience.
Hello.This article was really remarkable, particularly because I was browsing for thoughts on this matter last Wednesday.