UVA 12167: Proving Equivalences —— 强连通分量

传送门

题目大意:

现在有 $n$ 个命题,他们之间存在推导关系,比如命题 $p$ 可以推命题 $q$ 。现在已经给出了 $m$ 个推导关系,问至少还需要多少次推导,才能使所有命题两两互推。

通俗一点讲,就是给出一个 $n$ 个点 $m$ 条边的有向图,问至少还需添加多少条边,使得有向图里的点两两互达。

输入格式:

第一行一个整数 $T$ 代表测试数据总数。

对于每一组测试数据,第一行两个数 $n$ 和 $m$ 。紧接着的 $m$ 行每行两个整数 $a,\ b$ ,代表一个已知的推导关系 $a$ -> $b$ 。

输出格式:

对于每一组测试数据,输出一行一个整数,代表最少还需的推导次数。

测试样例:

Input
2
4 0
3 2
1 2
1 3
Output
4
2

分析:

这是非常有意思的一道题。首先我们只要看出这道题的实质(也就是上面的题面翻译)就已经成功了一半了。

对于这道题,我们首先要用 Tarjan 算法求出这个有向图的强连通分量。因为强连通分量里的点是两两互达的,所以我们只需要考虑如何加最少的边使得各个强连通分量两两互达

结论是:新建的 $scc$ 图中入度为 $0$ 的点的个数出度为 $0$ 的点的个数$max$

为什么呢?

我们可以考虑:假设现在我们是要对几个独立的点加最少的边是它们两两互达,最少的策略是这样:


再考虑本题的情况。因为缩点之后,一个出度为 $0$ 的点不可能到达另一个出度为 $0$ 的点,一个入度为 $0$ 的点也不可能到达另一个入度为 $0$ 的点,所以我们可以把图简化成这样(图中每一个点代表一个强连通分量,灰色的边是原有的边,红色的边是还需添加的边):


所以答案就是出度为 $0$ 的点的个数与入度为 $0$ 的点的个数的较大值。

代码:

#include <bits/stdc++.h>
using namespace std;

template<class _T> inline void read(_T &_x) {
  int _t, _flag = 0;
  while ((_t = getchar()) != '-' && (_t < '0' || _t > '9'));
  if (_t == '-')  _t = getchar(), _flag = 1;
  _x = _t - '0';
  while ((_t = getchar()) >= '0' && _t <= '9')
    _x = _x * 10 + _t - '0';
  if (_flag)  _x = -_x;
}

typedef long long ll;

const int MAX_N = 50000 + 100, INF = 0x3f3f3f3f;
struct Edge {
  int v, next;
} edge[MAX_N << 1];
int head[MAX_N], kk = 1, idx, cnt_scc, sccno[MAX_N], ins[MAX_N], dfn[MAX_N], low[MAX_N], n, m;
int in[MAX_N], out[MAX_N], ans;
stack<int> s;

inline void addedge(int u, int v) {
  edge[kk] = (Edge) {v, head[u]}, head[u] = kk++;
}

void init() {
  kk = 1, idx = cnt_scc = ans = 0;
  memset(head, 0, sizeof(head));
  memset(sccno, 0, sizeof(sccno));
  memset(ins, 0, sizeof(ins));
  memset(dfn, 0, sizeof(dfn));
  memset(low, 0, sizeof(low));
  memset(in, 0, sizeof(in));
  memset(out, 0, sizeof(out));
  while (!s.empty())  s.pop();
}

void Tarjan(int u) {
  int v;
  dfn[u] = low[u] = ++idx;
  s.push(u);
  ins[u] = 1;
  for (int i = head[u]; i; i = edge[i].next) {
    int v = edge[i].v;
    if (!dfn[v]) {
      Tarjan(v);
      low[u] = min(low[u], low[v]);
    }
    else if (ins[v])  low[u] = min(low[u], dfn[v]);
  }
  if (dfn[u] == low[u]) {
    ++cnt_scc;
    while (u != v) {
      v = s.top();
      s.pop();
      ins[v] = 0;
      sccno[v] = cnt_scc;
    }
  }
}

void solve() {
  if (cnt_scc == 1) {
    printf("%d\n", ans);
    return;
  }
  for (int u = 1; u <= n; ++u) {
    for (int i = head[u]; i; i = edge[i].next) {
      int v = edge[i].v;
      if (sccno[v] != sccno[u]) {
        ++out[sccno[u]], ++in[sccno[v]];
      }
    }
  }
  int a = 0, b = 0;
  for (int i = 1; i <= cnt_scc; ++i) {
    if (!in[i]) ++a;
    if (!out[i])  ++b;
  }
  ans = max(a, b);
  printf("%d\n", ans);
}

int main() {
  int T;
  read(T);
  while (T--) {
    init();
    read(n), read(m);
    for (int i = 1; i <= m; ++i){
      int a, b;
      read(a), read(b);
      addedge(a, b);
    }
    for (int i = 1; i <= n; ++i) {
      if (!dfn[i])  Tarjan(i);
    }
    solve();
  }
}