首页 > 代码库 > UVa 11504 - Dominos
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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。