很明显缩完点之后入度为0的点是必须要通知的，也仅需要通知入度为0的点==
其实第二个邻接表是不用的，只用统计into数组即可
1 #include2 #include 3 #include 4 #include 5 using namespace std; 6 stack s; 7 int Now,Head[2005],Next[2005],Point[2005]; 8 int _now,_head[2005],_next[2005],_point[2005]; 9 int sccno[2005],lowlink[2005],pre[2005],dfs_clock,scc_cnt;10 int Value[2005],Minx[2005],Into[2005];11 void Add(int x,int y)12 {13 Next[++Now]=Head[x];14 Head[x]=Now;15 Point[Now]=y;16 }17 void add(int x,int y)18 {19 _next[++_now]=_head[x];20 _head[x]=_now;21 _point[_now]=y;22 }23 void dfs(int u)24 {25 int i,v;26 pre[u]=lowlink[u]=++dfs_clock;27 s.push(u);28 for (i=Head[u];i;i=Next[i]){29 v=Point[i];30 if (!pre[v]){31 dfs(v);32 lowlink[u]=min(lowlink[u],lowlink[v]);33 }34 else if (!sccno[v])35 lowlink[u]=min(lowlink[u],lowlink[v]);36 }37 if (lowlink[u]==pre[u]){38 ++scc_cnt;39 while (1){40 v=s.top(); s.pop();41 sccno[v]=scc_cnt;42 Minx[scc_cnt]=min(Minx[scc_cnt],Value[v]);43 if (v==u) break;44 }45 }46 }47 int main()48 {49 int n,m,i,j,v,ans,x,y,tmp;50 while (~scanf("%d%d",&n,&m)){51 memset(Head,0,sizeof(Head));52 memset(_head,0,sizeof(_head));53 memset(Into,0,sizeof(Into));54 memset(Minx,0x3f,sizeof(Minx));55 Now=_now=0;56 for (i=1;i<=n;i++) scanf("%d",&Value[i]);57 for (i=1;i<=m;i++){58 scanf("%d%d",&x,&y);59 Add(x,y);60 }61 dfs_clock=scc_cnt=0;62 memset(sccno,0,sizeof(sccno));63 memset(pre,0,sizeof(pre));64 while (!s.empty()) s.pop();65 for (i=1;i<=n;i++)66 if (!pre[i]) dfs(i);67 for (i=1;i<=n;i++)68 for (j=Head[i];j;j=Next[j]){69 v=Point[j];70 if (sccno[v]!=sccno[i]){71 add(sccno[i],sccno[v]);72 Into[sccno[v]]++;73 }74 }75 ans=tmp=0;76 for (i=1;i<=scc_cnt;i++)77 if (Into[i]==0) tmp++,ans+=Minx[i];78 printf("%d %d\n",tmp,ans);79 }80 return 0;81 }
题目链接：