Zth's Blog

记录学习路上的点滴

0%

Codeforces Round

发表于 分类于

题目链接

题目

题目描述

给定一个$n$个点， $m$条边的有向无环图， 要求删除一些边， 使剩下的边构成的子图$S$中包含尽量多的点， 输出这个点数

删边的要求如下

  1. 每个点的出度和入度除非本来就是$0$， 否则必须变化
  2. $S$中的任和两个点$u, v$， 要么存在$u$到$v$的路径， 要么存在$v$到$u$的路径

数据范围

$1 \leq n \leq 2 \times 10^5$

$0 \leq m \leq 2 \times 10^5$

题解

思路

要做出这道题， 我们首先需要观察出一点：$S$必然是一条链

证明： 使用归纳法， 如果有$1$条边， 那么显然成立；$2$条边时也显然必是链； $3$条时也显然 ……

考虑度数减少的限制， $S$中除了链的起点外的其他点在原图中的入度必须大于等于$2$， 除了终点外的其他点在原图中的出度必须大于等于$2$。 然后我们就可以$dp$了， $dp$状态间的转移可以构成一张有向无环图， 就是原图， 我们对原图求一下拓扑序然后$dp$就可以了

代码

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
#include <iostream>
#include <cstdio>
#include <queue>
#include <algorithm>

int n, m;
int head[200005], tot;
struct Edge
{
    int from, to, next;
} edge[200005];
int in[200005], inv[200005], out[200005];
int tp[200005], num;
std:: queue<int> que;
int res[200005], ans = 1;

void Addedge(int u, int v)
{
    in[v] ++;
    out[u] ++;
    inv[v] ++;

    edge[++ tot] = (Edge){u, v, head[u]};

    head[u] = tot;
}

void Topo()
{
    for(int i = 1; i <= n; i ++)
        if(!inv[i])
            que.push(i);

    while(! que.empty())
    {
        int u = que.front();
        que.pop();

        tp[++ num] = u;

        for(int i = head[u]; i; i = edge[i].next)
        {
            int v = edge[i].to;

            inv[v] --;

            if(!inv[v]) que.push(v);
        }
    }

    std:: reverse(tp + 1, tp + n + 1);
}

void Solve()
{
    Topo();



    for(int j = 1; j <= n; j ++)
    {
        int u = tp[j];

        res[u] = 1;

        if(out[u] < 2) continue;

        for(int i = head[u]; i; i = edge[i].next)
        {
            int v = edge[i].to;

            if(in[v] < 2) continue;

            res[u] = std:: max(res[u], res[v] + 1);
        }

        ans = std:: max(ans, res[u]);
    }

    printf("%d\n", ans);
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= m; i ++)
    {
        int u, v;
        scanf("%d%d", &u, &v);

        Addedge(u, v);
    }

    Solve();

    return 0;
}