1269c.cpp

威士忌的HDU题解.大概有260多题的源码。对于学习非常有好处。

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

void bfs()   
{   
    int temp,i,s;   
       
    while(!SQ.empty())   
    {   
        s=SQ.front();   
        SQ.pop_front();   
        Mark[s]=true;   
        total++;   
        for(i=0;i<v[s].size();i++)   
        {   
            temp=v[s][i];   
            if(!Mark[temp])   
                SQ.push_back(temp);   
        }   
    }   
}   
void nbfs()   
{   
    int temp,i,s;   
       
    while(!SQ.empty())   
    {   
        s=SQ.front();   
        SQ.pop_front();   
        Mark[s]=true;   
        total++;   
        for(i=0;i<nv[s].size();i++)   
        {   
            temp=nv[s][i];   
            if(!Mark[temp])   
                SQ.push_back(temp);   
        }   
    }   
}   

int main()   
{   
    int n,m,s,e,i;   
    bool flag;   
       
    v.resize(10010);  
    nv.resize(10010);  
    SQ.resize(100010);  
    while(scanf("%d %d",&n,&m)==2 )   
    {   
    	if(n==0 && m==0)
    		break;
        for(i=0;i<10010;i++) 
        { 
            v[i].clear();   
            nv[i].clear();   
        } 
        while(!SQ.empty()) 
            SQ.pop_front(); 
        memset(Mark,false,sizeof(Mark));   
        flag=true;   
        for(i=0;i<m;i++)   
        {   
            scanf("%d %d",&s,&e);   
            v[s].push_back(e);   
            nv[e].push_back(s);   
        }   
        total=0;   
        SQ.push_back(s);   
        bfs();   
        if(total!=n)   
            flag=false;   
        if(flag)   
        {   
            total=0;   
            memset(Mark,false,sizeof(Mark));   
            while(!SQ.empty()) 
                SQ.pop_front();  
            SQ.push_back(s);   
            nbfs();   
            if(total!=n)   
                flag=false;   
        }   
        if(flag)     
            printf("Yes\n");       
        else    
            printf("No\n");     
    }   
    return 0;   
}