Codeforces 950E Data Center Maintenance 强连通分量

题目链接

题意

有\(n\)个信息中心，每个信息中心都有自己的维护时间\((0\leq t\lt h)\)，在这个时刻里面的信息不能被获得。

每个用户的数据都有两份备份，放在两个相异的信息中心（维护时间也相异）。

现要挑选出信息中心的一个尽量小的子集，使得将这个子集的维护时间向后推移一个小时后，不会导致问题（存在一个用户，其数据所在的两个信息中心维护时间相同）。

思路

强连通分量

考虑每个用户的信息存放的两个信息中心，\(u,v\)：

如果调整其中任何一个的时间不会导致与另外一个产生冲突，就说明是安全的；

否则若\(u\)调整后与\(v\)产生冲突，则一旦调整\(u\)就必须调整\(v\)，于是加一条边\(<u,v>\).

在得到的图上跑\(tarjan\)再缩点后得到强连通分量，答案就是新的图中 出度为\(0\)的并且\(size\)最小 的一块\(SCC\)。道理显然。

Code

#include <bits/stdc++.h>

#define F(i, a, b) for (int i = (a); i < (b); ++i)

#define F2(i, a, b) for (int i = (a); i <= (b); ++i)

#define dF(i, a, b) for (int i = (a); i > (b); --i)

#define dF2(i, a, b) for (int i = (a); i >= (b); --i)

#define maxn 100010

using namespace std;

typedef long long LL;

int dfn[maxn], low[maxn], ne[maxn], belong[maxn], a[maxn], sz[maxn], scc, cnt, tot, outd[maxn];

stack<int> s;

bool in[maxn];

struct Edge { int from, to, ne; }edge[maxn<<1];

void add(int u, int v) {

    edge[tot] = {u, v, ne[u]};

    ne[u] = tot++;

}

void tarjan(int u) {

    dfn[u] = low[u] = ++cnt;

    in[u] = true;

    s.push(u);

    for (int i = ne[u]; ~i; i = edge[i].ne) {

        int v = edge[i].to;

        if (!dfn[v]) {

            tarjan(v);

            low[u] = min(low[u], low[v]);

        }

        else if (in[v]) low[u] = min(low[u], dfn[v]);

    }

    if (low[u]==dfn[u]) {

        ++scc;

        while (true) {

            int v = s.top(); in[v] = false; s.pop();

            belong[v] = scc; ++sz[scc];

            if (u==v) break;

        }

    }

}

void contrast() {

    F(i, 0, tot) {

        int u = edge[i].from, v = edge[i].to;

        if (belong[u]==belong[v]) continue;

        ++outd[belong[u]];

    }

}

int main() {

    memset(ne, -1, sizeof ne);

    int n, m, h, u, v;

    scanf("%d%d%d", &n, &m, &h);

    F2(i, 1, n) scanf("%d", &a[i]);

    F(i, 0, m) {

        scanf("%d%d", &u,&v);

        if (a[u]>a[v]) swap(u, v);

        if (a[v]-a[u]==1) add(u, v);

        if (a[v]-a[u]==h-1) add(v, u);

    }

    F2(i, 1, n) if (!dfn[i]) tarjan(i);

    contrast();

    int ans=n+1, p=-1;

    F2(i, 1, scc) {

        if (!outd[i]) {

            if (sz[i]<ans) ans=sz[i], p=i;

        }

    }

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

    F2(i, 1, n) if (belong[i]==p) printf("%d ", i); puts("");

    return 0;

}