并查集 （上）
学习kruskal的时候我们学习了并查集，那时候都是不带权值的。今天找了一些并查集的题目写了下，写题时也参考了大牛的博客
1.Rank of Tetris
HDU-1811（链接）
这个题用到拓扑结构和并查集，并查集主要是处理‘=’的关系。注意输出的时候，因为信息中同时包含冲突且信息不完全，就输出"CONFLICT"。 注意这里就好了。
代码如下：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<string>
#include<queue>
#include<vector>
#include<stack>
#include<list>
#include<map>
#include<set>
using namespace std;
const int maxn=10000+5;
const int INF = 1e9;
struct node
{
int x,y;
char ch;
//node(int xx,char hh,int yy):x(xx),ch(hh),y(yy) {};
} s[maxn];
vector<int> p[maxn];
int pre[maxn],in[maxn],sum,n;
void init()
{
int i;
for(i=0; i<n; i++)
{
pre[i]=i;
}
}
int Find(int x)
{
return x==pre[x]?x:pre[x]=Find(pre[x]);
}
bool comb(int x,int y)
{
x=Find(x);
y=Find(y);
if(x==y)
return false;
else
{
pre[y]=x;
return true;
}
}
void top_sort()
{
int i;
bool fg=0;
queue<int> q;
for(i=0; i<n; i++)
{
if(in[i]==0&&pre[i]==i)
q.push(i);
}
while(!q.empty())
{
int t=q.front();
if(q.size()>1) fg=1;
q.pop();
sum--;
for(i=0; i<p[t].size(); i++)
{
int u=p[t][i];
in[u]--;
if(in[u]==0)
q.push(u);
}
}
if(sum>0) cout<<"CONFLICT";
else if(fg) cout<<"UNCERTAIN";
else cout<<"OK";
cout<<endl;
}
int main()
{
int m,i;
while(~scanf("%d %d",&n,&m))
{
init();
sum=n;
memset(p,0,sizeof(p));
memset(in,0,sizeof(in));
for(i=0; i<m; i++)
{
scanf("%d %c %d",&s[i].x,&s[i].ch,&s[i].y);
if(s[i].ch=='='&&comb(s[i].x,s[i].y))
sum--;
}
for(i=0; i<m; i++)
{
int fx=Find(s[i].x);
int fy=Find(s[i].y);
if(s[i].ch=='=')
continue;
if(s[i].ch=='>')
{
p[fx].push_back(fy);
in[fy]++;
}
else
{
p[fy].push_back(fx);
in[fx]++;
}
}
top_sort();
}
}
2.Portal HDU 3938
带权值，我们用num数组记录，然后将输入的数据进行排序
代码如下：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<string>
#include<queue>
#include<vector>
#include<stack>
#include<list>
#include<map>
#include<set>
using namespace std;
const int maxn1=10000+5;
struct node
{
int a,b,c;
bool friend operator < (const node &x,const node &y)
{
return x.c<y.c;
}
node () {}
} s[50005];
struct dd
{
int x,id;
bool friend operator < (const dd &x,const dd &y)
{
return x.x<y.x;
}
} p[maxn1];
int pre[maxn1],num[maxn1];
long long ans[maxn1];
int Find(int x)
{
return x==pre[x]?x:pre[x]=Find(pre[x]);
}
int main()
{
int n,m,q;
while(scanf("%d%d%d",&n,&m,&q)!=EOF)
{
int x,y,z;
for(int i=1; i<=m; i++)
{
scanf("%d%d%d",&x,&y,&z);
s[i].a=x;
s[i].b=y;
s[i].c=z;
}
for(int i=1; i<=q; i++)
{
scanf("%d",&p[i].x);
p[i].id=i;
}
sort(s+1,s+m+1);
sort(p+1,p+q+1);
for(int i=1; i<=n; i++)
{
pre[i]=i;
num[i]=1;
}
long long sum = 0;
int j=1;
for(int i=1; i<=q; i++)
{
while(j<=m)
{
if(s[j].c>p[i].x) break;
int fx=Find(s[j].a);
int fy=Find(s[j].b);
if(fx!=fy)
{
pre[fx]=fy;
sum+=num[fx]*num[fy];
num[fy]+=num[fx];
}
j++;
}
ans[p[i].id]=sum;
}
for(int i=1; i<=q; i++)
printf("%lld\n",ans[i]);
}
return 0;
}
Virtual Friends
HDU 3172
水题！！！
代码如下：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<string>
#include<queue>
#include<vector>
#include<stack>
#include<list>
#include<map>
#include<set>
using namespace std;
const int maxn = 100000 +5 ;
int pre[maxn],num[maxn];
map<string, int > m;
void init()
{
int i;
for(i=0; i<maxn; i++)
{
pre[i]=i;
num[i]=1;
}
m.clear();
}
int Find ( int x)
{
return x==pre[x]?x:pre[x]=Find(pre[x]);
}
int main()
{
int t,n;
while(~scanf("%d",&t))
{
while(t--)
{
init();
scanf("%d",&n);
int cot=1;
string a,b;
while(n--)
{
cin>>a>>b;
if(m[a]==0) m[a]=cot++;
if(m[b]==0) m[b]=cot++;
int fx = Find(m[a]);
int fy = Find(m[b]);
if(fx!=fy)
{
pre[fx]=fy;
num[fy]+=num[fx];
}
cout<<num[fy]<<endl;
}
}
}
}
Dragon Balls
HDU 3635
强力推荐这题 在我们更新根节点的时候，也要更新移动的次数
代码如下：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<string>
#include<queue>
#include<vector>
#include<stack>
#include<list>
#include<map>
#include<set>
using namespace std;
const int maxn = 10000 +5 ;
int pre[maxn],num[maxn],mov[maxn];
int Find(int x)
{
if(x!=pre[x])
{
int t=pre[x];
pre[x]=Find(pre[x]);
mov[x]+=mov[t];
return pre[x];
}
return x;
}
void join(int x,int y)
{
int fx=Find(x);
int fy=Find(y);
if(fx!=fy)
{
pre[fx]=fy;
num[fy]+=num[fx];
mov[fx]++;
}
}
void init(int n)
{
int i;
for(i=1; i<=n; i++)
{
pre[i]=i;
num[i]=1;
mov[i]=0;
}
}
int main()
{
int t;
while(~scanf("%d",&t))
{
int cot=1;
while(t--)
{
int n,m,a,b;
char c[5];
scanf("%d%d",&n,&m);
init(n);
printf("Case %d:\n",cot++);
while(m--)
{
scanf("%s",c);
if(c[0]=='T')
{
scanf("%d%d",&a,&b);
join(a,b);
}
else
{
scanf("%d",&a);
int ans=Find(a);
printf("%d %d %d\n",pre[ans],num[ans],mov[a]);
}
}
}
}
}
Junk-Mail Filter
HDU 2473
删除节点，
首先将0~n-1的根节点设为n~2n-1，将2n~2n+m-1作为备用节点。删除操作时将x的根节点置为备用节点，然而实际上x的节点信息之前已经映射到x+n中，那么x+n的兄弟节点的根节点信息依然保留了下来。详细看这：http://blog.csdn.net/check_check_check/article/details/52297098
代码如下：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<string>
#include<queue>
#include<vector>
#include<stack>
#include<list>
#include<map>
#include<set>
using namespace std;
const int maxn = 1e5 +5 ;
const int maxm = 1e6 +5;
int pre[maxn*2+maxm];
int cot,n,m;
inline void init()
{
for(int i=0; i<n; i++)
pre[i]=i+n;
for(int i=n; i<n+n+m; i++)
pre[i]=i;
}
inline int Find (int x)
{
return pre[x]==x?x:pre[x]=Find(pre[x]);
}
inline void unin(int x,int y)
{
int fx=Find(x);
int fy=Find(y);
if(fx!=fy)
pre[fx]=fy;
}
inline void Clear(int x)
{
pre[x]=cot++;
}
int main()
{
int k=0;
while(scanf("%d%d",&n,&m),n+m)
{
init();
char ch;
cot=n+n;
int a,b;
while(m--)
{
getchar();
scanf("%c",&ch);
if(ch=='M')
{
scanf("%d%d",&a,&b);
unin(a,b);
}
else
{
scanf("%d",&a);
Clear(a);
}
}
set<int> s;
for(int i=0; i<n ; i++)
s.insert(Find(i));
printf("Case #%d: %d\n",++k,s.size());
}
return 0;
}并查集的题目还有一些还没写，比如POJ的食物链。之后会也写上
