【并查集之判断连通无环图】

HDU-1272 | HDU-1325 小希的迷宫 | Is it a tree ?

http://acm.hdu.edu.cn/showproblem.php?pid=1272

http://acm.hdu.edu.cn/showproblem.php?pid=1325

判断一张图是否是一颗树(连通，无环)的两个关键点：

不存在环路(对于有向图，不存在环路也就意味着不存在强连通子图)

满足边数加一等于顶点数的规律(不考虑重边和指向自身的边)——根唯一

其实我觉得这两个题目差不多啊，只不过1325把边换成了有向边，我觉得ok啊，没什么差别把其实是不同的，比如1 - 2, 2 - 3,4 - 2这样你如果不加任何优化结果是以3为根得树了（连老大），很明显跟不是聚来的，而是发散的，就是根得入度是0，所以1325加上一个入度得判断就行了（而且常见并查集和入度出度放一块啊）还有欧拉回路问题，以后都会去回顾一下

先来个简单的1272

#include <iostream>
#include <string.h>
#include <cstdio>
using namespace std;
const int maxn = 1e5 + 1e4;
int pre[maxn],s[maxn],vis[maxn];
int pcnt,ecnt,retflag;

void init()
{
    for(int i = 0;i < maxn;i++)
    {
        pre[i] = i;
        s[i] = 1;
        vis[i] = 0;
    }
    pcnt = ecnt = 0;
    retflag = 1;
}
int Find(int x)
{
    while(x != pre[x])
    {
        pre[x] = pre[pre[x]];
        x = pre[x];
    }
    return x;
}
void join(int a,int b)
{
    int u = Find(a);
    int v = Find(b);
    if(u == v)
    {
        retflag = 0;
    }
    else
    {
        if(!vis[a] && u == a)vis[a] = 1,pcnt++;
        if(!vis[b] && v == b)vis[b] = 1,pcnt++;
        ecnt++;
        if(s[u] > s[v])
        {
            pre[v] = u;
            s[u] += s[v];
        }
        else
        {
            pre[u] = v;
            s[v] += s[u];
        }
    }
}
int main()
{
    int a,b;
    init();
    while(~scanf("%d%d",&a,&b))
    {
        if(a == b && a == -1)break;

        if(a == b && a == 0)
        {
            if(ecnt == 0)printf("Yes
");
            else if(!retflag || ecnt + 1 != pcnt)
            {
                printf("No
");
            }
            else printf("Yes
");
            init();
        }
        else if(!retflag)
        {
            continue;
        }
        else
        {
            join(a,b);
        }
    }
    return 0;
}

基本上大部分都是模板得嵌套，所以就不分开讲了，虽然有路径压缩和平衡树得保持，但是时间仍然很慢，因为我不知道数据得范围，所以每次更新次数非常多GG，1325就会改变一些了（然后点的个数和边的个数我都一块放在里面判断了，觉得拿出来太费时间）

1325

#include <iostream>
#include <string.h>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxn = 1e6;
int pre[maxn],vis[maxn],in[maxn];
int pcnt,ecnt,retflag;

void init(int n = 1e5 + 1e4)
{
    for(int i = 0;i <= n;i++)
    {
        pre[i] = i;
        vis[i] = 0;
        in[i] = 0;
    }
    pcnt = ecnt = 0;
    retflag = 1;
}
int Find(int x)
{
    while(x != pre[x])
    {
        pre[x] = pre[pre[x]];
        x = pre[x];
    }
    return x;
}
void join(int a,int b)
{
    int u = Find(a);
    int v = Find(b);
    if(u == v)
    {
        if(!vis[u])vis[u] = 1,pcnt++;
        retflag = 0;
    }
    else
    {
        if(!vis[a] && u == a)vis[a] = 1,pcnt++;
        if(!vis[b] && v == b)vis[b] = 1,pcnt++;
        ecnt++;
        if(++in[b] > 1)retflag = 0;
        pre[u] = v;
    }
}
int main()
{
    int a,b,cas = 1;
    int retn = 0;
    init();
    while(~scanf("%d%d",&a,&b))
    {
        if(a < 0 || b < 0)break;
        retn = max(retn,max(a,b));
        if(a == b && a == 0)
        {
            if(ecnt == 0 && pcnt == 0)printf("Case %d is a tree.
",cas++);
            else if(!retflag || ecnt + 1 != pcnt)
            {
                printf("Case %d is not a tree.
",cas++);
            }
            else printf("Case %d is a tree.
",cas++);
            init(retn);
        }
        else if(!retflag)
        {
            continue;
        }
        else
        {
            join(a,b);
        }
    }
    return 0;
}

1325这个题，有一个坑人得地方就是结束得判断是a或b有一个是负数，我说为什么老是re，原来访问了a[-2]……

其他的都比较好说