这题WA了好几遍。原因是num数组没有初始化。。果然细节很重要啊。。
题目意思是求传递数最大的有多少孩子,并输出他们的序号。我们先在原图上用Tarjan算法求出强连通分量,然后建立反向图,并求出反向图中各个点的入度,传递数的最大值肯定是在这些入度为0的点中。
#include <stdio.h> #include <iostream> #include <algorithm> #include <string.h> #include <math.h> #include <stack> #include <vector> #define LL long long #define M 5005 #define INF 999999999 using namespace std; vector<int> G[M],G2[M]; int dfn[M],low[M],sccno[M],scc_cnt,index; int num[M],temp[M],sum; bool vis[M]; stack<int> s; //用Tarjan算法求强连通分量 void Tarjan(int u) { dfn[u]=low[u]=++index; s.push(u); for(int i=0;i<G[u].size();i++) { int v=G[u][i]; if(dfn[v]==0) { Tarjan(v); low[u]=min(low[u],low[v]); } else if(!sccno[v]) { low[u]=min(low[u],dfn[v]); } } if(low[u]==dfn[u]) { scc_cnt++; for(;;) { int x=s.top(); s.pop(); sccno[x]=scc_cnt; temp[scc_cnt]++; //记录这个强连通分量中有多少个点 if(x==u) break; } } } void find_scc(int n) { index=scc_cnt=0; memset(sccno,0,sizeof(sccno)); memset(dfn,0,sizeof(dfn)); memset(temp,0,sizeof(temp)); for(int i=0;i<n;i++) if(dfn[i]==0) Tarjan(i); } //深搜求出入度为0的点的传递数 int dfs(int u) { vis[u]=true; sum+=temp[u]; for(int i=0;i<G2[u].size();i++) { int v=G2[u][i]; if(vis[v]==false) { dfs(v); } } return sum; } int main() { int n,m; int in0[M]; int t; scanf("%d",&t); for(int count=1;count<=t;count++) { scanf("%d%d",&n,&m); for(int i=0;i<n;i++) { G[i].clear(); G2[i].clear(); } for(int i=0;i<m;i++) { int u,v; scanf("%d%d",&u,&v); G[u].push_back(v); } find_scc(n); for(int i=1;i<=scc_cnt;i++) in0[i]=1; for(int u=0;u<n;u++) { for(int i=0;i<G[u].size();i++) { int v=G[u][i]; if(sccno[u]!=sccno[v]) { G2[sccno[v]].push_back(sccno[u]); in0[sccno[u]]=0; } } } printf("Case %d: ",count); int Max=-1; memset(num,-1,sizeof(num)); for(int i=1;i<=scc_cnt;i++) { sum=0; if(in0[i]) { memset(vis,false,sizeof(vis)); int q=dfs(i); num[i]=q; Max=max(Max,q); } } printf("%d\n",Max-1); int flag=0; for(int i=0;i<n;i++) { if(num[sccno[i]]==Max) { if(flag==0) { printf("%d",i); flag=1; } else printf(" %d",i); } } printf("\n"); } return 0; }