HDU1272+BFS

题意就是要求给定的一张图是否是棵树。。。
BFS一遍即可+树的特征。
有一组BT数据。。。
View Code
  1 /*
  2 
  3 */
  4 #include<stdio.h>
  5 #include<string.h>
  6 #include<stdlib.h>
  7 #include<algorithm>
  8 #include<iostream>
  9 #include<queue>
 10 #include<vector>
 11 #include<map>
 12 #include<math.h>
 13 typedef long long ll;
 14 //typedef __int64 int64;
 15 const int maxn = 100005;
 16 const int maxm = 1005;
 17 const int inf = 0x7FFFFFFF;
 18 const double pi = acos(-1.0);
 19 const double eps = 1e-8;
 20 using namespace std;
 21 int vis[ maxn ];
 22 struct node{
 23     int u,next;
 24 }edge[ maxn<<2 ];
 25 int cnt ,head[ maxn ];
 26 int v[ maxn ];
 27 
 28 void init(){
 29     cnt = 0;
 30     memset( head,-1,sizeof( head ));
 31     memset( vis,0,sizeof( vis ) );
 32 }
 33 
 34 void addedge( int a,int b ){
 35     edge[ cnt ].u = b;
 36     edge[ cnt ].next = head[ a ];
 37     head[ a ] = cnt++;
 38 }
 39 
 40 bool bfs( int st,int sum ){
 41     memset( vis,0,sizeof( vis ) );
 42     queue<int>q;
 43     q.push( st );
 44     vis[st] = 1;
 45     while( !q.empty() ){
 46         int now = q.front();
 47         q.pop();
 48         for( int i=head[ now ];i!=-1;i=edge[ i ].next ){
 49             int nxt = edge[ i ].u;
 50             if( vis[ nxt ]==0 ){
 51                 vis[ nxt ] = 1;
 52                 q.push( nxt );
 53             }
 54         }
 55     }
 56     for( int i=0;i<sum;i++ ){
 57         if( vis[ v[i] ]==0 ) return false;
 58     }
 59     return true;
 60 }
 61         
 62 int main(){
 63     int a,b;
 64     while( scanf("%d%d",&a,&b)==2 ){
 65         if( a==-1&&b==-1 ) break;
 66         init();
 67         int sum = 0;
 68         int nedge = 0;
 69         nedge++;
 70         if( vis[a]==0 ){
 71             vis[a]++;
 72             v[ sum ] = a;
 73             sum++;
 74         }
 75         if( vis[b]==0 ){
 76             vis[b]++;
 77             v[ sum ] = b;
 78             sum++;
 79         }
 80         addedge( a,b );
 81         addedge( b,a );
 82         if( a==0&&b==0 ){
 83             printf("Yes\n");
 84             continue;
 85         }
 86         while( scanf("%d%d",&a,&b)==2 ){
 87             if( a==0&&b==0 ) break;
 88             nedge++;
 89             if( vis[a]==0 ){
 90                 vis[a]++;
 91                 v[ sum ] = a;
 92                 sum++;
 93             }
 94             if( vis[b]==0 ){
 95                 vis[b]++;
 96                 v[ sum ] = b;
 97                 sum++;
 98             }
 99             addedge( a,b );
100             addedge( b,a );
101         }
102         if( sum-1==nedge&&bfs( v[0],sum )==true ){
103             printf("Yes\n");
104         }
105         else{
106             printf("No\n");
107         }
108     }
109     return 0;
110 }
keep moving...