1269 迷宫城堡.cpp

来自「威士忌的HDU题解.大概有260多题的源码。对于学习非常有好处。」· C++ 代码 · 共 84 行

#include <queue>  
#include <vector>  
#include <cstdio>  
using namespace std;  
queue<int> SQ;  
vector< vector<int> > v;  
bool Mark[10010];  
bool cir[10010];
int total;  
bool bCircle;

void dfs(int s)  
{  
    int temp,i;  
      
    if(bCircle)
   		return;
	if(Mark[s])
		return;
    if(cir[s])
    {
    	bCircle=true;
    	return;
    }
   	Mark[s]=true;
  	
	for(i=0;i<v[s].size();i++)
	{
		dfs(v[s][i]);
	}	
	if(bCircle)
	{
		cir[s]=true;
		SQ.push(s);
		total++;
	}
}

int main()  
{  
    int n,m,s,e,i;    
      
    v.resize(10010); 
    while(scanf("%d %d",&n,&m)==2 )  
    {  
    	if(n==0 && m==0)
    		break;
    	for(i=0;i<10010;i++)
    	{
        	v[i].clear();  
    	}   
        memset(Mark,false,sizeof(Mark));
        memset(cir,false,sizeof(cir));
        for(i=0;i<m;i++)  
        {  
            scanf("%d %d",&s,&e);  
            v[s].push_back(e);  
        }  
        for(i=0;i<v[s].size();i++)
        	SQ.push(v[s][i]);
		total=1;  
		cir[s]=true;
		bCircle=false; 
		
 		while(!SQ.empty())
 		{
 			if(total==n)
 				break;
   			s=SQ.front();  
    		dfs(s);  
    		bCircle=false;
    		SQ.pop();
 		}
 		while(!SQ.empty())     
			SQ.pop();
        
        if(total==n)    
            printf("Yes\n");      
        else   
            printf("No\n");    
    }  
    return 0;  
}