hdu 1116 并查集和欧拉路径-白红宇

hdu 1116 并查集和欧拉路径

阅读量：6094 次

发布时间：2019-06-20

本文共 913 字，大约阅读时间需要 3 分钟。

---恢复内容开始---

把它看成是一个图

只是需要欧拉路径就可以了首尾能连成一条线即可

如果要判断这个图是否连通得用并查集

在hrbust oj里面看答案学到的方法不用各种for循环套着判断能否循环

只需要在union的时候做做调整让比较大的父亲节点的父亲节点等于小的父亲节点向1靠拢就可以

但是在这里面是向出现过的最小的字母的排序靠拢所以要记录

而且for循环26个字母的时候只对出现过的字母做判断它是否与最小的字母可以连通

#include
     
      #include
      
       #include
       
        #include
        using namespace std;int ru[30];int chu[30];int fa[30];int vis[30];void init(){    for(int i=1;i<=26;i++)    {        ru[i]=0;        chu[i]=0;        fa[i]=i;        vis[i]=0;    }}int find(int i){    return fa[i]==i?i:find(fa[i]);}void un(int a,int b){    int aa=find(a);    int bb=find(b);    if(aa>bb)        fa[aa]=bb;    else fa[bb]=aa;}int main(){    int t;    scanf("%d",&t);    while(t--)    {        int n;        scanf("%d",&n);        char s[2000];        init();        int minn=26;        for(int i=0;i