UVa 11504 - Dominos

题目：有一些多米诺骨牌，现在告诉你他们的相邻顺序，问最少推几次可以把他们全部推倒。

分析：图论，强连通分量。强连通分量上的某点被推到，整个分量都会倒。

            求强连通分量，然后缩点，剩下的“点”中每个入度为0的点都要用手推倒；（必要性）

            再者，在缩点后的图中，每次找到一个入度为0的点推倒后，不会产生新的入度为0的点；（充分性）

           （新产生的入度为0的点，之前入度一定不为0，那么它的前驱倒下后，他也必然倒下，不会留下来）

            综上，要推倒所有入度为0的点，所有点就倒下了。

说明：注意是有向图。

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>

using namespace std;

//link_define
typedef struct enode
{
	int    point;
	enode* next;
}edge;
edge  E[100001];
edge* H[100001];
int   edge_count;

void link_initial()
{
	edge_count = 0;
	memset(E, 0, sizeof(E));
	memset(H, 0, sizeof(H));
}

void link_add(int a, int b)
{
	E[edge_count].point = b;
	E[edge_count].next = H[a];
	H[a] = &E[edge_count ++];
} 
//link_end

int  use[100001],dfn[100001],low[100001],stk[100001],set[100001];
int  s_id,times,top;  
void tarjan(int i, int j)   
{  
    dfn[i] = low[i] = ++ times;  
    use[i] = 1;  
    stk[++ top] = i;  
    for (edge* p = H[i] ; p ; p = p->next) {  
        if (!dfn[p->point]) {  
            tarjan(p->point, 0);  
            low[i] = min(low[i], low[p->point]);  
        }else if (use[p->point])
            low[i] = min(low[i], dfn[p->point]);  
    }  
    if (dfn[i] == low[i]) {  
        s_id ++;  
        do {
            j = stk[top --];
            use[j] = 0;  
            set[j] = s_id;  
        }while (j != i);  
    }  
}

int in[100001];
 
int main()
{
	int t,n,m,a,b;
	while (~scanf("%d",&t))
	while (t --) {
		scanf("%d%d",&n,&m);
		link_initial();
		for (int i = 1 ; i <= m ; ++ i) {
			scanf("%d%d",&a,&b);
			link_add(a, b);
		}
		
		//强连通分量   
	    s_id = times = top = 0;  
	    memset(dfn, 0, sizeof(dfn));  
	    memset(use, 0, sizeof(use));  
	    for (int i = 1 ; i <= n ; ++ i)  
	        if (!dfn[i])  
	            tarjan(i, 0);
		
		memset(in, 0, sizeof(in));
		for (int i = 1 ; i <= n ; ++ i)
			for (edge *p = H[i] ; p ; p = p->next)
				if (set[i] != set[p->point])
					in[set[p->point]] ++;
		int count = 0;
		for (int i = 1 ; i <= s_id ; ++ i)
			count += !in[i];
		
		printf("%d\n",count);
	}
	return 0;
}

UVa 11504 - Dominos

原文：http://blog.csdn.net/mobius_strip/article/details/41015357