Summer Holiday HDU - 1827 强连通分量+缩点

To see a World in a Grain of Sand 
And a Heaven in a Wild Flower, 
Hold Infinity in the palm of your hand 
And Eternity in an hour. 
                  —— William Blake 

听说lcy帮大家预定了新马泰7日游，Wiskey真是高兴的夜不能寐啊，他想着得快点把这消息告诉大家，虽然他手上有所有人的联系方式，但是一个一个联系过去实在太耗时间和电话费了。他知道其他人也有一些别人的联系方式，这样他可以通知其他人，再让其他人帮忙通知一下别人。你能帮Wiskey计算出至少要通知多少人，至少得花多少电话费就能让所有人都被通知到吗？ 

Input

多组测试数组，以EOF结束。 
第一行两个整数N和M（1<=N<=1000, 1<=M<=2000），表示人数和联系对数。 
接下一行有N个整数，表示Wiskey联系第i个人的电话费用。 
接着有M行，每行有两个整数X，Y，表示X能联系到Y，但是不表示Y也能联系X。 

Output

输出最小联系人数和最小花费。 
每个CASE输出答案一行。 

Sample Input

12 16
2 2 2 2 2 2 2 2 2 2 2 2 
1 3
3 2
2 1
3 4
2 4
3 5
5 4
4 6
6 4
7 4
7 12
7 8
8 7
8 9
10 9
11 10

Sample Output

3 6

AC的C++程序如下:

#include<bits/stdc++.h>
using namespace std;
const int N=1005;
int cnt,money,res;
int low[N],num[N],dfn,sccp[N],degree[N];
int sccno[N],stack1[N],price[N],top;
vector<int> G[N];
void dfs(int u)
{
	stack1[top++]=u;
	low[u]=num[u]=++dfn;
	for(int i=0;i<G[u].size();i++)
	{
		int v=G[u][i];
		if(!num[v])
		{
			dfs(v);
			low[u]=min(low[v],low[u]);
		}
		else if(!sccno[v])
		{
			low[u]=min(low[u],num[v]);
		}
	}
	if(low[u]==num[u])
	{
		int min1=price[u];
		cnt++;
		while(1)
		{
			int v=stack1[--top];
			sccno[v]=cnt;
			min1=min(min1,price[v]);
			if(u==v) break;	
		}
		sccp[cnt]=min1;//每个SCC中最小钱数 
	}
 } 
 void Tarjan(int n)
 {
 	cnt=top=dfn=money=res=0;
 	memset(sccno,0,sizeof(sccno));
 	memset(num,0,sizeof(num));
 	memset(low,0,sizeof(low));
 	memset(sccp,0,sizeof(sccp));
 	memset(degree,0,sizeof(degree));
 	
 	for(int i=1;i<=n;i++)
 	{
 		if(!num[i]) dfs(i);
	 }
	 for(int i=1;i<=n;i++)
	 {
	 	for(int j=0;j<G[i].size();j++)
	 	{
	 		if(sccno[i]!=sccno[G[i][j]]) degree[sccno[G[i][j]]]=1;//统计入度 
		 }	  
	  } 
	  for(int i=1;i<=cnt;i++)
	  {
	  	if(degree[i]==0)
	  	{
	  		res++;
	  		money+=sccp[i];
		  }
	  }
 }
 int main()
 {
 	int n,m,u,v;
    while(~scanf("%d%d",&n,&m))
    {
    	for(int i=1;i<=n;i++) G[i].clear();
    	for(int i=1;i<=n;i++) scanf("%d",&price[i]);
    	for(int i=0;i<m;i++)
    	{
    		scanf("%d%d",&u,&v);
    		G[u].push_back(v);
		}
		Tarjan(n);
		printf("%d %d\n",res,money);
	}
	 return 0;
 }