hdu 5438 Ponds 拓扑序+简单dfs

点击打开链接

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio> 
#include <queue> 
#include <vector> 
using namespace std;
const int M =100101;
long long degree[M];
long long value[M];
long long p,m; //节点数和边数 
vector<long> g[M];// 
long long cnt,num;//统计连通分量的节点个数 
void Topo()
{
	queue<long> q;//队列保存编号 
	for(int i=1;i<=p;i++)
	{
		if(degree[i]<=1)
		{
			q.push(i);
			value[i]=0;//价值置为0 		
		}
	}
	while(!q.empty())
	{
		int k=q.front();
		q.pop(); 
		for(int i=0;i<g[k].size();i++)//与k相连的degeree都减去1 
		{
			degree[g[k][i]]--;
			if(degree[g[k][i]]<=1&&value[g[k][i]]) 
			{
				value[g[k][i]]=0;//防止重复入队 
			//	cout<<"入队"<<g[k][i]<<endl;
				q.push(g[k][i]);	
			}	
		}	
		
	} 
}
void dfs(long s)
{
	for(int i=0;i<g[s].size();i++)
	{
		if(value[g[s][i]])
		{
			
			cnt+=value[g[s][i]];
			value[g[s][i]]=0;//表示已经访问过了 
			num++;		
			dfs(g[s][i]);	
		}
	}
}

int main()
{
    int t;
    cin>>t;
    while(t--)
    { 	
    	memset(g,0,sizeof(g));
    	memset(degree,0,sizeof(degree));
    	cin>>p>>m;
    	for(int i=1;i<=p;i++)
    	{
    		cin>>value[i];
		}
		while(m--)
		{
			int a,b;
			cin>>a>>b;		
			g[a].push_back(b);//双向边 
			g[b].push_back(a);
			degree[a]++;
			degree[b]++;
		}
		Topo();
		long long ans=0;
    	for(int i=1;i<=p;i++)
		{	
			cnt=0;		
			if(value[i])//没有被删除 &&没有统计过 
			{
				num=0; 
				dfs(i);		
				if(num%2)
				{ 
					ans+=cnt;	
				}				
			}	
		} 
		printf("%I64d\n",ans);
	
	}
    return 0;
}