首页 > 代码库 > HDU 4496 D-City(并查集,逆思维)
HDU 4496 D-City(并查集,逆思维)
题目
熟能生巧。。。常做这类题,就不会忘记他的思路了。。。
//可以反过来用并查集,还是逐个加边,但是反过来输出。。。我是白痴。。。。、又没想到//G++能过,C++却wa,这个也好奇怪呀。。。#include<stdio.h>#include<string.h>int fx,fy,r,bin[10010];int x[100010],y[100010],n,m,i,count,ans[100010],j;int find(int x){ //改成这样就不会超时了么好奇怪为什么 if(bin[x] == x)return x; return bin[x] = find(bin[x]); /*超时到哭,,,why? r=x; while(bin[r]!=r) { r=bin[r]; } return r; */}void merge(int x,int y){ fx=find(x); fy=find(y); if(fx!=fy) { bin[fx]=fy; ans[j]=ans[j-1]+1; } else ans[j]=ans[j-1]; j++;}int main(){ while(scanf("%d %d",&n,&m)!=EOF) { memset(ans,0,sizeof(ans)); for(i=0;i<n;i++) { bin[i]=i; } for(i=0;i<m;i++) { scanf("%d %d",&x[i],&y[i]); } j=0; for(i=m-1;i>=0;i--) { merge(x[i],y[i]); } for(i=j-2;i>=0;i--) printf("%d\n",n-ans[i]); printf("%d\n",n); } return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。