先给链接POJ 2186 Popular Cows ,POJ 1236 Network of Schools
这两道题都是经典的强连通分量问题,本人都采用了伟大的SCC Tarjan算法.
关于SCC Tarjan算法 可以参见本博的处理SCC(强连通分量问题)的Tarjan算法
先说POJ 2186 Popular Cows
(不看这题,直接跳到1236的题解)
题意:每个Cow都梦想成为牛群里最知名的奶牛,在一个有N(1 <= N <= 10,000) 头牛的牛群里,给出最多M(1 <= M <= 50,000) 个数对(A,B)告诉你A认为B是有名的,并且名气可以传递,若果A认为B有名,B认为C有名,则A也会认为C有名,即使在输入的数对中没有给出这段关系,你的任务是计算出被所有牛认为是有名的牛的个数.
引用另一位仁兄Headacher的题解中的一部分(参见PKU POJ 2186 Popular Cows 强连通分量 ),讲的很好,很精辟
算法证明：
1：假设a和b都是最受欢迎的cow，那么，a欢迎b，而且b欢迎a，于是，a和b是属于同一个连通分量内的点，所有，问题的解集构成一个强连通分量。
2：如果某个强连通分量内的点a到强连通分量外的点b有通路，因为b和a不是同一个强连通分量内的点，所以b到a一定没有通路，那么a不被b欢迎，于是a所在的连通分量一定不是解集的那个连通分量。
3：如果存在两个独立的强连通分量a和b，那么a内的点和b内的点一定不能互相到达，那么，无论是a还是b都不是解集的那个连通分量，问题保证无解。
4：如果图非连通，那么，至少存在两个独立的连通分量，问题一定无解。
这样我们便的得到了初步的解决方案
- 用Tarjan算法求出强连通分量,设立Belong数组,用并查集将在同一强连通分量的节点并在一起.
- 建树,遍历所有输入中的点对(A,B)如果AB分属两个不同的强连通分量,则belong[B]是belong[A]的父节点
- 显然,如果点对(A,B),A所在的强连通分量(用并查集指定,getf(A))指向的元素和”A指向的强连通分量“不属于同一强连通分量,则不构成树结构,无解.
- 遍历所有强连通分量,如果存在一个强连通分量指向自己,则它是最著名的强连通分量
- 遍历所有节点,如果属于答案强连通分量,计数器累加,最后输出答案
本人的代码很丑,用的前向星,第一次写前向星,被yxc同志指为”光建图排序就要\(N\log (N)\)“所以用的计数排序,建图部分是为了前向星而前向星,直接无视即可
MY CODE:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 |
/* Problem: 2186 User: comzyh Memory: 1204K Time: 63MS Language: C++ Result: Accepted */ #include <cstdio> #include <cstring> #include <cstdlib> struct think{ int f,t; }; int N,M,R; think link0[50009],link[50009]; int times[10009],timesr[10009],first[10009];//计数排序 //SCC Tarjan int low[10009],dfn[10009],instack[10009],belong[10009]; int father[10009];//下标和元素均是强连通分量编号 //Count int NOANS,ANS,NANS; int count[10009]; int f[10009]; int stap[50009]; int top,nSCC,rtime/*时间戳*/; void tarjan(int x); int getf(int x); void add(int x,int y);//add x to y int main(){ int i,j; scanf("%d%d",&N,&M); memset(times,0,sizeof(times)); //以下大段计数排序,构图(前向星) for (i=1;i<=M;i++){ scanf("%d%d",&link0[i].f,&link0[i].t); times[link0[i].f]++; } for (i=1;i<=N;i++){ times[i]+=times[i-1]; timesr[i]=times[i-1]; first[i]=times[i-1]+1; }//取值时使用 for (i=1;i<=M;i++) link[++timesr[link0[i].f]]=link0[i]; //计数排序完成 //Tarjan top=nSCC=rtime=0; memset(dfn,0,sizeof(dfn)); for (i=1;i<=N;i++)//初始化并查集 f[i]=i; for (i=1;i<=N;i++) if (!dfn[i]) tarjan(i); NOANS=0;//不是无解 for (i=1;i<=nSCC;i++)//使用并查集思想,存储树 father[i]=i; //处理所有数对 (A,B) 不同强连通分量之间的任意有向边为强连通分量之间的有向边 for (i=1;i<=M;i++) if (getf(link[i].f)!=getf(link[i].t)){//属于不同强连通分量 if (father[belong[link[i].f]]==belong[link[i].f]){ father[belong[link[i].f]]=belong[link[i].t];//建树的过程 continue; }else if (father[belong[link[i].f]]!=belong[link[i].t]){ //如果以个强连通分量有出度 >1说明该题无解 NOANS=1;//无解 break; } father[belong[link[i].f]]=belong[link[i].t]; } /* for (i=1;i<=nSCC;i++) printf("%3d 's Father=%4d\n",i,father[i]); */ NANS=0; for (i=1;i<=nSCC;i++) if (father[i]==i){//最终Father是自己的只有最有名的强连通分量 ANS=i; NANS++; } if (NOANS || (NANS>1)) printf("0"); else printf("%d",count[ANS]);输出 system("pause"); } void tarjan(int x){//这个参见Comzyh的Tarjan讲解 int i,t; dfn[x]=low[x]=++rtime; instack[x]=1; stap[++top]=x; for (i=first[x];i<=timesr[x];i++){ t=link[i].t; if (!dfn[t]){ tarjan(t); if (low[t]<low[x]) low[x]=low[t]; }else if (instack[t] && (dfn[t]<low[x])) low[x]=dfn[t]; } if (dfn[x]==low[x]){ nSCC++; do { count[nSCC]++; t=stap[top--]; add(t,x); belong[t]=nSCC; instack[t]=0; }while (t!=x); } } int getf(int x){//并查集 if (f[x]==x) return x; return f[x]=getf(f[x]); } void add(int x,int y){//add x to y if (getf(x)==getf(y)) return ; f[getf(x)]=getf(y); } |
再说POJ 1236 Network of Schools
题意及解法(转自极限定律),写的很好
题目大意:N(2<N<100)各学校之间有单向的网络,每个学校得到一套软件后,可以通过单向网络向周边的学校传输,问题1：初始至少需要向多少个学校发放软件,使得网络内所有的学校最终都能得到软件.2,至少需要添加几条传输线路(边),使任意向一个学校发放软件后,经过若干次传送,网络内所有的学校最终都能得到软件。
具体算法：先用Korasaju Algorithm求出有向图所有的强连通分量(当然Comzyh是用的Tarjan),然后将所有的强连通分量缩成一个点(缩点),这样原来的有向图就缩成了一个DAG图(有向无环图);用2个数组分别记录新生成的DAG图中的每个顶点(包括原来的顶点和强连通分量的缩点)是否有出边和入边,最后遍历每个顶点,如果没有入边,则ans1++;如果没有出边,ans2++.最后所求即为ans1和max(ans1,ans2).
注意如果最终仅有一个强连通分量,显然第二问应输出0而不是1
这道题的代码比上一题简洁的多了
MY CODE:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 |
/* Problem: 1236 User: comzyh Memory: 240K Time: 0MS Language: C++ Result: Accepted */ #include <cstdio> #include <cstring> #include <cstdlib> int tab[101][101]; int DFN[101],LOW[101],stack[200],instack[200]; int f[101]; int belong[101]; int top,RB,RT;//栈顶,最后一个强连通分量编号,最后一个时间戳 int ein[101],eout[101],ans,ans1,ans2; int N; //Function void Tarjan(int x); int getf(int x); inline void add(int x,int y);//add x to y int main() { int i,j,to; scanf("%d",&N); memset(tab,0,sizeof(tab)); for (i=1;i<=N;i++) while (scanf("%d",&to),to) tab[i][++tab[i][0]]=to; // memset(DFN,0,sizeof(DFN)); memset(instack,0,sizeof(instack)); top=RB=RT=0; for (i=1;i<=N;i++) f[i]=i; for (i=1;i<=N;i++) if (!DFN[i]) Tarjan(i); //for (i=1;i<=N;i++)printf("%4d belong to %4d\n",i,belong[i]); memset(ein,0,sizeof(ein)); memset(eout,0,sizeof(eout)); for (i=1;i<=N;i++) if (tab[i][0]) { eout[belong[i]]=1; for (j=1;j<=tab[i][0];j++) if (getf(i)!= getf(tab[i][j]))ein[belong[tab[i][j]]]=1; } ans1=ans2=0; for (i=1;i<=RB;i++) { if (!ein[i] )ans1++; if (!eout[i])ans2++; } ans=(ans1>ans2)?ans1:ans2; if (RB==1)ans=0;//如果就一个分量,显然不用再连接 printf("%d\n%d",ans1,ans); system("pause"); } void Tarjan(int x) { int i,t;//t= top / to 多用途, stack[++top]=x; DFN[x]=LOW[x]=++RT; instack[x]=1; for (i=1;i<=tab[x][0];i++) { t=tab[x][i]; if (!DFN[t]) { Tarjan(t); if (LOW[t] < LOW[x]) LOW[x] = LOW[t]; } else if (instack[t] && DFN[t]<LOW[x]) LOW[x]=DFN[t]; } if (LOW[x] == DFN[x]) { RB++; do { t=stack[top--]; add(t,x); belong[t]=RB; instack[t]=0; }while(t != x); } } int getf(int x) { if (f[x] == x)return x; else return f[x]=getf(f[x]); } inline void add(int x,int y)//add x to y { int fx=getf(x),fy=getf(y); if (fx == fy)return ; f[fx]=fy; } |
原创文章，转载请注明： 转载自Comzyh的博客
本文链接地址: POJ 2186 & 1236 强连通分量 Tarjan算法
LZ的几篇博客都看了，很喜欢
谢谢支持