题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2767

题意：问最少加多少边可以让所有点都相互连通。

题解：如果强连通分量就1个直接输出0，否者输出入度为0的缩点，出度为0的缩点和的最大值

#include <iostream>

#include <cstring>

#include <cstdio>

using namespace std;

const int N = 2e4 + 10;

const int M = 5e4 + 10;

struct Edge {

    int v, next;

}edge[M];

int head[N], e;

int Low[N], DFN[N], Belong[N], num[N], Stack[N];

int Index, top, scc;

int In[N], Out[N];

bool Instack[N];

void init() {

    memset(head, -1, sizeof(head));

    e = 0;

}

void add(int u, int v) {

    edge[e].v = v;

    edge[e].next = head[u];

    head[u] = e++;

}

void Tarjan(int u) {

    int v;

    Low[u] = DFN[u] = ++Index;

    Stack[top++] = u;

    Instack[u] = true;

    for(int i = head[u]; i != -1; i = edge[i].next) {

        v = edge[i].v;

        if(!DFN[v]) {

            Tarjan(v);

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

        } else if(Instack[v]) Low[u] = min(Low[u], DFN[v]);

    }

    if(Low[u] == DFN[u]) {

        scc++;

        do {

            v = Stack[--top];

            Instack[v] = false;

            Belong[v] = scc;

            num[scc]++;

        } while(v != u);

    }

}

int main() {

    int t;

    scanf("%d", &t);

    while(t--) {

        int n, m;

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

        init();

        for(int i = 0; i < m; i++) {

            int s1, s2;

            scanf("%d%d", &s1, &s2);

            add(s1, s2);

        }

        memset(DFN, 0, sizeof(DFN));

        memset(Instack, false, sizeof(Instack));

        memset(Belong, 0, sizeof(Belong));

        memset(num, 0, sizeof(num));

        memset(In, 0, sizeof(In));

        memset(Out, 0, sizeof(Out));

        scc = 0, Index = 0, top = 0;

        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 != -1; j = edge[j].next) {

                int v = edge[j].v;

                if(Belong[i] != Belong[v]) {In[Belong[v]]++, Out[Belong[i]]++;}

            }

        }

        int mxin = 0, mxout = 0;

        for(int i = 1; i <= scc; i++) {

            if(In[i] == 0) mxin++;

            if(Out[i] == 0) mxout++;

        }

        if(scc == 1) printf("0\n");

        else printf("%d\n", max(mxin, mxout));

    }

    return 0;

}