发布于 

Equivalent Sets

Equivalent Sets

hdu 3836

题目来源: hdu

分析

题目给出了几个集合，并且给出了几组它们之间的关系，要求至少需要在测定几次它们之间的关系(小于关系)，能够验证出它们是否相等。同时，题目给出可以通过$A < B & B < A $的方式来验证它们是否相等。

题目要求测定次数最小，那么什么情况下测量的次数会最小呢？或者说有哪些测量会是不必要的呢？我们假设两个集合之间的小于关系是一条有向边，那么当几个集合成环时，它们一定相等。而此时的边数也一定已经是最小了。

但是整个图最后一定要组成一个环吗?很明显，几个相交的环也能推出其中所有点的相等关系，因为等于关系是可以传递的。那么到底组成几个环最好呢？这该怎么算呢？

我们不妨想一下环的性质是什么呢？所有点的入度和出度都不为\(0\)。那么我们只要去掉为\(0\)的点便能成环。理论上，我们最好将入度为\(0\)的点和出度为\(0\)的点连在一起，但是有时候它们数目不一样，所以我们需要再将多出来的连接到任意一个点上即可。

不过这样成环后图一定联通吗？假设我们能分别用两条边生成两个不连通的环，那么可以证明我们用这两条边也能生成一整个环，所以一定存在最后的图联通的方案。但是若初始的图中就有一个环，那么就比较麻烦了。此时我们需要用Tarjan来求强连通分量，然后缩点，把其看成一个点即可。

因此，最后的答案是$ max(_1^n in_i, _1^n out_i) \(，\)in_i\(和\)out_i$记录的是每个强连通分量的入度和出度。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#include <iostream>
#include <stack>
#include <algorithm>
#include <cstring>

#define MAXN 20010

using namespace std;

struct Edge;

struct Node
{
    Edge *edge;
    int dfn, low, color;
    bool flag;

    Node()
    {
        flag = false;
        dfn = low = color = 0;
        edge = NULL;
    }
}node[MAXN];

struct Edge
{
    Node *from, *to;
    Edge *next;

    ~Edge()
    {
        delete next;
    }

    Edge(Node *from, Node *to):from(from),to(to),next(from->edge)   {}
};

int cnt = 0;

stack<Node *> s;
void Tarjan(Node *x)
{
    static int num = 0;
    x->low = x->dfn = ++num;
    x->flag = true;
    s.push(x);

    for (Edge *e = x->edge; e; e = e->next)
    {
        if (e->to->dfn==0)
        {
            Tarjan(e->to);
            x->low = min(x->low, e->to->low);
        }else if (e->to->flag)
            x->low = min(x->low, e->to->dfn);
    }

    if (x->dfn==x->low)
    {
        x->flag = false;
        x->color = ++cnt;

        while ( !s.empty() && s.top()!=x)
        {
            Node *v = s.top();
            v->color = cnt;
            v->flag= false;
            s.pop();
        }
        if (!s.empty())
            s.pop();
    }
}

int in[MAXN],out[MAXN];

int main()
{
    int n,m;
    while (cin >> n >> m)
    {
        memset(out,0,sizeof(out));
        memset(in,0,sizeof(in));
        for (int i = 1; i<=n; i++)
        {
            delete node[i].edge;
            node[i] = Node();
        }
        cnt = 0;

        for (int i = 1; i<=m; i++)
        {
            int x,y;
            cin >> x >> y;
            node[x].edge = new Edge(&node[x],&node[y]);
        }

        for (int i = 1; i<=n; i++)
            if (node[i].dfn==0)
                Tarjan(&node[i]);

        for (int i = 1; i<=n; i++)
        {
            for (Edge *e = node[i].edge; e; e = e->next)
                if (node[i].color!=e->to->color)
                {
                    out[node[i].color] ++;
                    in[e->to->color] ++;
                }
        }

        int ans[2];
        ans[0] = ans[1] = 0;
        
        for (int i = 1; i<=cnt; i++)
        {
            if (!in[i])
                ans[0]++;
            if (!out[i])
                ans[1]++;
        }
        if (cnt==1)
            cout << 0 << endl;
        else cout << max(ans[0],ans[1]) << endl;
    }
}
许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。

本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。

本站由 [@Songer](https://blog.songer.xyz/) 创建，使用 Stellar 作为主题。