hyz's blog
0%

CF 1020E Sergey's problem

发表于

题意

给一个可能有环（但肯定没有自环）的有向图，n($1 <= n <= 1e6$)个点，m($1 <= m <= 1e6$)条边，现在需要你选择一个点集，使得这些点之间没有连边，且这些点到点集之外的点的距离不超过2。

分析

首先任意选择一点A放到点集里面，则这个点指向的点都不能放到点集里面，我们从原图中删掉这些点，然后再从残余图中找点集，假设这个点集为M。假如点集M中存在一点B有指向A的边，为了处理掉这个冲突，我们删掉A，因为B到A指向的点的距离不超过2，所以保证覆盖了全图。假如不存在，那么我们就将点集M和A合并，也保证了覆盖全图。

代码

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
#include<bits/stdc++.h>
#define x first
#define y second
#define ok cout << "ok" << endl;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const long double PI = acos(-1.0);
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const double Eps = 1e-7;
const int N = 2e6+9;

int head[2][N], tot, n, m, u, v;
bool vis[N], used[N];;

void init() {
    tot = 0;
    memset(head, -1, sizeof head);
}

struct node {
    int to, nex;
}edge[N];

void addedge(int u, int v, int id) {
    edge[tot] = node{v, head[id][u]};
    head[id][u] = tot++;
}

void dfs(int u) {
    while(u <= n && vis[u]) u++;
    if(u == n + 1) return;
    used[u] = vis[u] = true;
    for(int i = head[0][u]; ~i; i = edge[i].nex) {
        v = edge[i].to;
        vis[v] = true;
    }
    dfs(u + 1);
    for(int i = head[1][u]; ~i; i = edge[i].nex) {
        v = edge[i].to;
        if(used[v]) {
            used[u] = false;
            break;
        }
    }
}

int main(void) {
    if(fopen("in", "r")!=NULL) {freopen("in", "r", stdin); freopen("out", "w", stdout);}
    while(~scanf("%d%d", &n, &m)) {
        init();
        for(int i = 0; i < m; i++) {
            scanf("%d%d", &u, &v);
            addedge(u, v, 0);
            addedge(v, u, 1);
        }
        dfs(1);
        vi ans;
        for(int i = 1; i <= n; i++)
            if(used[i])
                ans.push_back(i);
        printf("%d\n", (int)ans.size());
        for(int i = 0; i < ans.size(); i++)
            printf("%d%c", ans[i], " \n"[ans.size() - 1 == i]);
    }

    return 0;
}