题目大意：一个有向图，边(i,j)表示牛i认为牛j受欢迎，这种关系具有传递性。问：图中存在多少只牛被其他所有牛认为是受欢迎的？
很喜欢这种题……简洁的题面和清晰的题意，但足够一想想一天的。
思路是求强连通分支后缩点，再判断缩点后是否存在唯一出度数为0的点（也即最受欢迎牛群k），然后再判在反向图中，是否其余缩点从点k出发都可达。这里有个坑：如果总共只有一只牛，直接输出0。
具体实现上，分别尝试使用了CLRS上的两次DFS和tarjan来求强连通分支。另外，这题也是第一次写缩点，用了并查集，感觉有点累赘。
两次DFS：
|
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 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 |
#include<cstdio> #include<cstring> #include<queue> using namespace std; int n,m,ad[10001][10001],hd[10001],hdr[10001],a[10001],al,el,erl,f[10001],b[10001]; struct edge { int i,j,p; }e[50000],er[50000]; inline void adde(int i,int j) { e[el].i=i; e[el].j=j; e[el].p=hd[i]; hd[i]=el++; } inline void adder(int i,int j) { er[erl].j=j; er[erl].p=hdr[i]; hdr[i]=erl++; } int fi(int i) { if(f[i]<0) return i; else return f[i]=fi(f[i]); } inline void un(int a,int b) { int fa=fi(a),fb=fi(b); if(fa==fb) return; int na=f[fa],nb=f[fb]; if(na<nb) { f[fa]+=nb; f[fb]=fa; } else { f[fb]+=na; f[fa]=fb; } } void DFS(int i) { int j,k,l; b[i]=1; for(l=hd[i];l!=-1;l=e[l].p) { j=e[l].j; if(!b[j]) DFS(j); } a[al++]=i; } void DFSr(int i) { int j,k,l; b[i]=1; for(l=hdr[i];l!=-1;l=er[l].p) { j=er[l].j; if(!b[j]) { un(i,j); DFSr(j); } } } int main() { int i,j,k,l; while(~scanf("%d%d",&n,&m)) { memset(b,0,sizeof b); memset(hd,-1,sizeof hd); memset(hdr,-1,sizeof hdr); memset(f,-1,sizeof f); el=al=erl=0; while(m--) { scanf("%d%d",&i,&j); adde(i,j); adder(j,i); } if(n==1) { puts("0"); continue; } for(i=1;i<=n;i++) if(!b[i]) DFS(i); memset(b,0,sizeof b); for(i=al-1;i>-1;i--) if(!b[a[i]]) DFSr(a[i]); memset(hdr,-1,sizeof hdr); erl=0; memset(b,0,sizeof b); for(l=0;l<el;l++) { i=fi(e[l].i); j=fi(e[l].j); if(i!=j) { adder(j,i); b[i]=1; } } queue<int>Q; for(l=1;l<=n;l++) { i=fi(l); if(i==l&&!b[i]) Q.push(i); } if(Q.empty()||Q.size()>1) { puts("0"); continue; } k=Q.front(); while(!Q.empty()) { i=Q.front(); Q.pop(); for(l=hdr[i];l!=-1;l=er[l].p) { j=er[l].j; if(b[j]) { b[j]=0; Q.push(j); } } } for(i=1;i<=n&&!b[i];i++); if(i<=n) puts("0"); else printf("%d\n",-f[k]); } return 0; } |
tarjan（总感觉自己敲的东西有种山寨感？）：
|
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 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 |
#include<cstdio> #include<cstring> #include<queue> using namespace std; int n,m,hd[10001],hdr[10001],el,erl,dfn[10001],low[10001],b[10001],f[10001]; int st[10001],sl,tb[10001],d; struct edge { int i,j,p; }e[50000],er[50000]; inline void adde(int i,int j) { e[el].i=i; e[el].j=j; e[el].p=hd[i]; hd[i]=el++; } inline void adder(int i,int j) { er[erl].j=j; er[erl].p=hdr[i]; hdr[i]=erl++; } int fi(int i) { if(f[i]<0) return i; else return f[i]=fi(f[i]); } inline void un(int a,int b) { int fa=fi(a),fb=fi(b); if(fa==fb) return; int na=f[fa],nb=f[fb]; if(na<nb) { f[fa]+=nb; f[fb]=fa; } else { f[fb]+=na; f[fa]=fb; } } void tarjan(int i) { int j,k,l; dfn[i]=low[i]=d++; st[sl++]=i; tb[i]=1; for(l=hd[i];l!=-1;l=e[l].p) { j=e[l].j; if(dfn[j]==-1) { tarjan(j); low[i]=low[j]<low[i]?low[j]:low[i]; } else if(tb[j]) low[i]=low[j]<low[i]?low[j]:low[i]; } if(dfn[i]==low[i]) { while(1) { sl--; un(i,st[sl]); tb[st[sl]]=0; if(st[sl]==i) break; } } } int main() { int i,j,k,l; while(~scanf("%d%d",&n,&m)) { memset(hd,-1,sizeof hd); memset(hdr,-1,sizeof hdr); memset(b,0,sizeof b); memset(dfn,-1,sizeof dfn); memset(f,-1,sizeof f); memset(tb,0,sizeof tb); el=erl=sl=d=0; while(m--) { scanf("%d%d",&i,&j); adde(i,j); } if(n==1) { puts("0"); continue; } for(i=1;i<=n;i++) { if(dfn[i]==-1) tarjan(i); } for(l=0;l<el;l++) { i=fi(e[l].i); j=fi(e[l].j); if(i!=j) { adder(j,i); b[i]=1; } } queue<int>Q; for(l=1;l<=n;l++) { i=fi(l); if(i==l&&!b[i]) Q.push(i); } if(Q.empty()||Q.size()>1) { puts("0"); continue; } k=Q.front(); while(!Q.empty()) { i=Q.front(); Q.pop(); for(l=hdr[i];l!=-1;l=er[l].p) { j=er[l].j; if(b[j]) { b[j]=0; Q.push(j); } } } for(i=1;i<=n&&!b[i];i++); if(i<=n) puts("0"); else printf("%d\n",-f[k]); } return 0; } |
两种算法的耗时相近，但是两次DFS怎么会和一次DFS的tarjan差不多呢？实在不太明白…