题意：若出自己之外的其他牛都认为它很popular，那么它就是最popular了的。问最popular的牛有多少。
思路：设第 i 头牛合法，则与此牛在一个强连通分量里的牛均合法。若不存在这样的第 i 头牛，则答案为0。
所以我们先要处理出所有的强连通分量，然后缩点。则这些缩点构成的新图必定为有向无环图。若图连通且
只有一个出度为零的缩点，则此缩点代表的强连通分量内的点的数目即为答案，若不存这样的缩点，则答案为0。
有向图的强连通分量的求法感觉和无向图的很类似，故不在赘述。
#include#include #include #include #include #include #include #define LL long long #define ULL unsigned long long #define PI (acos(-1.0)) #define EPS (1e-10) using namespace std; struct N { int v,next; } e[5000100]; int head[1000100]; int id[1000100]; int rv[1000100]; int ty[1000100]; int ry[1000100]; bool mv[1000100]; int Top; void link(int u,int v) { e[Top].next = head[u]; e[Top].v = v; head[u] = Top++; } int dfs(int s,int d) { rv[s] = d; int p,depth = 10000100,temp; for(p = head[s]; p != -1; p = e[p].next) { if(rv[e[p].v] == -1) { temp = dfs(e[p].v,d+1); } else { temp = rv[e[p].v]; } if(temp < depth) depth = temp; } if(depth >= rv[s]) { ry[Top] = s; ty[s] = Top++; } else { ty[s] = Top; } return depth; } void bfs(int s) { queue q; q.push(s); mv[s] = true; int p ; while(q.empty() == false) { s = q.front(); q.pop(); for(p = head[s]; p != -1; p = e[p].next) { if(mv[e[p].v] == false) { mv[e[p].v] = true; if(ty[s] != ty[e[p].v]) { id[ty[s]]++; } q.push(e[p].v); } else if(ty[s] != ty[e[p].v]) { id[ty[s]]++; } } } } int main() { int n,m,i,u,v; //freopen("denur.txt","w",stdout); while(scanf("%d %d",&n,&m) != EOF) { memset(head,-1,sizeof(int)*(n+2)); memset(rv,-1,sizeof(int)*(n+2)); Top = 0; for(i = 0; i < m; ++i) { scanf("%d %d",&u,&v); link(v,u); } Top = 0; for(i = 1; i <= n; ++i) { if(rv[i] == -1) { dfs(i,1); } } memset(mv,false,sizeof(bool)*(n+2)); memset(id,0,sizeof(int)*(Top+2)); for(i = 1; i <= n; ++i) { if(mv[i] == false) { bfs(i); } } int ans = 0,site; for(i = 0; i < Top; ++i) { if(id[i] == 0) { ans++; site = i; } } if(ans != 1) { printf("0\n"); } else { for(ans = 0,i = 1; i <= n; ++i) { if(ty[i] == site) ans++; } printf("%d\n",ans); } } return 0; }
---------------------------------- 华丽丽的分割线 ----------------------------------
POJ的测试数据越来越让人不放心了. . . . . 有这么严重的BUG的代码都能过. . . . . . .
下面这份代码是正确的最起码比上面拿分正确. . . . . .错代码就不删了. . . . .
DFS过程中要讨论下一个点是不是已经属于某一个强连通分量了，若是则忽略，不是泽判断此点是否有反向边。
#include#include #include #include #include #include #include #define LL long long #define ULL unsigned long long #define PI (acos(-1.0)) #define EPS (1e-10) using namespace std; struct P { int u,v,w; }p[510]; struct N { int v,next; }e[5000100]; int head[1000100]; int id[1000100]; int rv[1000100]; int ty[1000100]; int ry[1000100]; bool mv[1000100]; int Top; void link(int u,int v) { e[Top].next = head[u]; e[Top].v = v; head[u] = Top++; } int dfs(int s,int d) { rv[s] = d; int p,depth = 10000100,temp; for(p = head[s]; p != -1; p = e[p].next) { if(rv[e[p].v] == -1) { temp = dfs(e[p].v,d+1); } else { if(ty[e[p].v] == -1) temp = rv[e[p].v]; else temp = 10000100; } if(temp < depth) depth = temp; } if(depth >= rv[s]) { ry[Top] = s; ty[s] = Top++; } else { ty[s] = Top; } return depth; } int dis[510]; const void sp(int s,int e,int n,int m) { if(ty[s] == ty[e]) { printf("0\n"); return ; } int i,j; bool mark; for(i = 0;i < Top; ++i) dis[i] = 5551111; dis[ty[s]] = 0; for(i = 0;i < Top; ++i) { mark = false; for(j = 0;j < m; ++j) { if(ty[p[j].u] != ty[p[j].v]) { if(dis[ty[p[j].u]] + p[j].w < dis[ty[p[j].v]]) { dis[ty[p[j].v]] = p[j].w + dis[ty[p[j].u]]; mark = true; } } } if(mark == false) break; } if(dis[ty[e]] >= 5551111) printf("Nao e possivel entregar a carta\n"); else printf("%d\n",dis[ty[e]]); } int main() { int n,m,i,u,v,k; //freopen("denur.txt","w",stdout); while(scanf("%d %d",&n,&m) && (n||m)) { memset(head,-1,sizeof(int)*(n+2)); memset(rv,-1,sizeof(int)*(n+2)); memset(ty,-1,sizeof(int)*(n+2)); Top = 0; for(i = 0; i < m; ++i) { scanf("%d %d %d",&p[i].u,&p[i].v,&p[i].w); link(p[i].u,p[i].v); } Top = 0; for(i = 1; i <= n; ++i) { if(rv[i] == -1) { dfs(i,1); } } scanf("%d",&k); for(i = 0;i < k; ++i) { scanf("%d %d",&u,&v); sp(u,v,n,m); } printf("\n"); } return 0; }