uva 11504（强连通分支）

题意：有一些骨牌，告诉你一些关系a->b表示a倒了b也会倒。然后问你最少要推到几个才能使所有的骨牌都倒下。

思路：这道题其实就是用的强连通分支的kosaraju算法。其实在了解了这个算法之后我们不妨来想想是怎么样的一个逻辑关系。第一遍dfs我们先得到了在vs数组中的拓扑关系。到了第二遍，我们就从拓扑序列高的先开始dfs（可以直观的了解到只要拓扑序列高的倒下了，那么拓扑序列低的必定倒下了）所以我们得到的dfs次数即为答案了。

代码如下：

/**************************************************
 * Author     : xiaohao Z
 * Blog     : http://www.cnblogs.com/shu-xiaohao/
 * Last modified : 2014-01-28 22:16
 * Filename     : uva_11504.cpp
 * Description     : 
 * ************************************************/

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <vector>
#include <set>
#include <map>
#define MP(a, b) make_pair(a, b)
#define PB(a) push_back(a)

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<unsigned int,unsigned int> puu;
typedef pair<int, double> pid;
typedef pair<ll, int> pli;
typedef pair<int, ll> pil;

const int INF = 0x3f3f3f3f;
const double eps = 1E-6;
const int LEN = 100000+10;
vector<int> vs, Map[LEN];
int vis[LEN], n, m, scct[LEN];

void dfs(int v){
    vis[v] = 1;
    for(int i=0; i<Map[v].size(); i++){
        if(!vis[Map[v][i]])dfs(Map[v][i]);
    }
    vs.PB(v);
}

void rdfs(int v, int f){
    vis[v] = 1;
    scct[v] = f;
    for(int i=0; i<Map[v].size(); i++){
        if(!vis[Map[v][i]])rdfs(Map[v][i], f);
    }
}

int scc(){
    memset(vis, 0, sizeof vis);
    vs.clear();
    for(int i=1; i<=n; i++)if(!vis[i])dfs(i);
    memset(vis, 0, sizeof vis);
    int f = 0;
    for(int i=vs.size()-1; i>=0; i--){
         if(!vis[vs[i]])rdfs(vs[i], f++);
    }
    return f;
}

int main()
{
//    freopen("in.txt", "r", stdin);

    int T, a, b;
    scanf("%d", &T);
    while(T--){
        for(int i=0; i<LEN; i++)Map[i].clear();
        scanf("%d%d", &n, &m);
           for(int i=0; i<m ;i++){
            scanf("%d%d", &a, &b);
            Map[a].PB(b);
        }
        printf("%d
", scc());
    }
    return 0;
}