异构体

Posted on Edited on In

题目大意：Paradeus 是一个新兴的宗教组织，该组织包含了𝑁 − 1个 Nyto，以及一个Mercurows 总共𝑁个人组成。每个 Nyto 都是被其他某个人传教而进入的 Paradeus，而 Mercurows 是宗教的创立者，也就是说 Mercurows 并没有被任何人拉进组织。这张记录了每个人是由谁拉进传销组织的记录被视为 Paradeus 的教义，一直被广为传颂。然而，随着岁月的流逝，有不法分子开始对 Paradeus 的教义发动了攻击。不法分子在 Paradeus 的教义上添加了一条记录(𝑎, 𝑏)，代表𝑏是由𝑎介绍入教的。这条记录的加入导致 Nyto 们发现教义已经不合法了。为了复兴教义，教徒们决定找到这条被不法分子加入的记录，并将其删除以恢复教义的荣光。 更具体的说，现在给定𝑁对记录(𝑎𝑖, 𝑏𝑖)代表是𝑎𝑖将𝑏𝑖拉入教的。注意这𝑁条记录包含了被不法分子添加的那一条。现在我们希望你找到某一条记录，使得删掉这条记录之后剩下的𝑁 − 1条记录能够形成合法的教义。要注意的是，教义并没有标注谁是 Mercurows，所以任何人都有可能是 Mercurows。

最开始写的假UFS，骗了四十分

正解是分段的，如果发现有环的话，根据题意，环一定只有一个，tarjan强联通分量求一个权值最大的点就好了

如果没有环，并且根据题意知道，某一个点的入度一定大于1，然后然后对他的两个儿子节点讨论一下就可以了

代码如下：

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
#include <cstdio>

using namespace std;

const int N = 1e5 + 66;

inline void dfs(int x)
{
    int i, y;
    vis[x] = 1;
    for (i = head[x]; i; i = e[i].nex)
    {
        y = e[i].ver;
        if (y == t) continue;
        dfs(y);
    }
    return;
}

int low[N], dfn[N], in[N], sta[N], tp, tot;
priority_queue<int>q;

inline void tarjan(int x)
{
    int i, y;
    dfn[x] = low[x] = ++ tot, in[x] = 1, sta[++ tp] = x;
    for (i = head[x]; i; i = e[i].nex)
    {
        y = e[i].ver;
        if (! dfn[y])
        {
            tarjan(y);
            low[x] = min(low[x], low[y]);
        }
        else if (in[y]) low[x] = min(low[x], dfn[y]);
    }
    if (low[x] == dfn[x])
    {
        do {
            y = sta[tp --], in[y] = 0;
            q.push(d[y]);
        } while (y != x);
        if(q.size() > 1) res = max(res, q.top());
        while(q.size()) q.pop();
    }
    return;
}

signed main()
{
    int i, pd, x, y;
    n = read();

    for (i = 1; i <= n; ++ i)
    {
        x = read(), y = read();
        add_edge(x, y, i), d[y] = i;
    }
    
    for (i = 1; i <= n; ++ i)
    {
        if (deg[i] > 1) pd = 1, t = i;
        if (! deg[i]) st = i;
    }

    if (pd == 1)
    {
        int number = 0;
        for (i = 1; i <= n; ++ i) if (e[i].ver == t) a[++ number] = i;
        dfs(st);
        if (! vis[e[a[1]].frm]) res = a[1];
        else
        {
            if (! vis[e[a[2]].frm]) res = a[2];
            else res = max(a[1], a[2]);
        }
    }
    else for (i = 1; i <= n; ++ i) if (! dfn[i]) tarjan(i);
    
    put(res);
    return 0;
}