题解：UVA12167 Proving Equivalences

将问题可以进行转化：求一张 $n$ 个点 $m$ 条边的有向图上还需要增加几条边才可以使图强连通。

由于是一张有向图，所以我们需要求出强连通分量，然后进行缩点并记录出度或入度为 $0$ 的点的个数，最后两者取 $\max$ 输出答案。

但需要注意的点有两个：

若原图只有 $1$ 个强连通分量，则需要特判输出 $0$。
原图不保证连通，因此进行 dfs 的时候需要循环扫一遍。

给个代码：

#include <iostream>
#include <cstdio>
#include <stack>
#include <cstring>
#define init(x) memset (x,0,sizeof (x))
using namespace std;
const int MAXN = 1e5 + 5;
int t,n,m,cnt,times,scc_cnt,num1,num2;
int dfn[MAXN],low[MAXN],vis[MAXN],in[MAXN],out[MAXN];
int head[MAXN << 1],to[MAXN << 1],nxt[MAXN << 1];
stack <int> s;
void _add (int u,int v);
void tarjan (int u);
int main ()
{
    //freopen (".in","r",stdin);
    //freopen (".out","w",stdout);
    scanf ("%d",&t);
    while (t--)
    {
        cnt = times = scc_cnt = num1 = num2 = 0;
        init (dfn);init (low);init (vis);init (in);init (out);
        init (head);init (to);init (nxt);
        scanf ("%d%d",&n,&m);
        for (int i = 1;i <= m;++i)
        {
            int x,y;scanf ("%d%d",&x,&y);
            _add (x,y);
        }
        for (int i = 1;i <= n;++i)
            if (!dfn[i]) tarjan (i);
        for (int i = 1;i <= n;++i)//缩点 
        {
            for (int j = head[i];j;j = nxt[j])
            {
                int v = to[j];
                if (vis[i] != vis[v])//不在同一个强连通分量中 
                    ++out[vis[i]],++in[vis[v]];
            }    
        }
        if (scc_cnt == 1)
        {
            printf ("0\n");
            continue;
        }
        for (int i = 1;i <= scc_cnt;++i)
        {
            if (!in[i]) ++num1;
            if (!out[i]) ++num2;
        }
        printf ("%d\n",max (num1,num2));
    }
    return 0;
}
void _add (int u,int v)
{
    to[++cnt] = v;
    nxt[cnt] = head[u];
    head[u] = cnt;
}
void tarjan (int u)
{
    low[u] = dfn[u] = ++times;
    s.push (u);
    for (int i = head[u];i;i = nxt[i])
    {
        int v = to[i];
        if (!dfn[v])
        {
            tarjan (v);
            low[u] = min (low[u],low[v]);
        }
        else if (!vis[v]) low[u] = min (low[u],dfn[v]);//对于已经求出 scc 的点，直接忽略 
    }
    if (low[u] == dfn[u])//u 是强连通分量中第一个被发现的点
    {
        ++scc_cnt;
        while (1)
        {
            int x = s.top ();s.pop ();
            vis[x] = scc_cnt;
            if (x == u) break;
        }
    } 
}