HDU 2767 Proving Equivalences(强连通+缩点)

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

       题意是给了n个点m条有向边，问最少再加多少条边可以使整个图变为强连通图。

       思路不是很难，先让强连通分量缩为一个点，然后得到一个新图，要让图变为强连通图，那么就不会存在入度和出度为0的点，所以对新图算一下出入度，取一个最大值就好了，特判原图本身就是一个强连通图的情况。

AC代码：

#include <bits/stdc++.h>
#define maxn 20005
#define maxm 50005
using namespace std;
struct Node{
  int to, next;
}Edge[maxm];
int head[maxn], num;
int ind[maxn], ond[maxn], low[maxn], dfn[maxn], pre[maxn], tot, cnt;
bool vis[maxn];
stack<int> s;
int T,n,m;

void init(){
  for(int i=0;i<=n;i++){
    head[i] = -1;
    pre[i] = ind[i] = ond[i] = dfn[i] = low[i] = 0;
    vis[i] = false;
  }
  num = tot = cnt = 0;
}

void add(int u,int v){
  Edge[num].to = v;
  Edge[num].next = head[u];
  head[u] = num ++;
}

void tarjan(int x){
  dfn[x] = low[x] = ++ cnt;
  vis[x] = true;
  s.push(x);
  for(int i=head[x];i!=-1;i=Edge[i].next){
    int to = Edge[i].to;
    if(!dfn[to]){
      tarjan(to);
      low[x] = min(low[x], low[to]);
    }
    else if(vis[to]) low[x] = min(low[x], dfn[to]);
  }
  if(low[x] == dfn[x]){
    tot ++;
    while(1){
      int xx = s.top();
      s.pop();
      vis[xx] = false;
      pre[xx] = tot;
      if(xx == x) break;
    }
  }
}

int main()
{
  scanf("%d",&T);
  while(T--){
    scanf("%d%d",&n,&m);
    init();
    for(int i=0;i<m;i++){
      int u, v;
      scanf("%d%d",&u,&v);
      add(u, v);
    }
    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 to = Edge[j].to;
        if(pre[to] != pre[i]){
          ind[pre[to]] ++;
          ond[pre[i]] ++;
        }
      }
    }
    int t1 = 0, t2 = 0;
    for(int i=1;i<=tot;i++){
      if(!ind[i]) t1 ++;
      if(!ond[i]) t2 ++;
    }
    if(tot == 1) puts("0");
    else printf("%d\n", max(t1, t2));
  }
  return 0;
}