POJ 1308 搜索
题意：给你一堆边，有向边，然后这个图是否构成一颗树。
他这里树的定义是这样的：只有一个入度为0的点，是根节点。
每一个节点（除根节点）都只有一条边指向他，也就是入度等于1。
从根节点到任意一个节点的路径是唯一的。
满足上面三个要求的话就是树。
OK。那就可以搞了，A了之后看DISCUSS里面都说是并查集搞的，我是直接爆搜的。
思路：首先找出入度为0的点，如果有多个，那么不是树。
然后找度数大于1的，如果有，那么不是树。
最后从根节点爆搜一遍，看节点是否都只访问到一次。
注意0 0 的时候代表空树，他也是一颗树，我想这是这道题唯一的trick了。
#include <set>#include <map>#include <stack>#include <cmath>#include <queue>#include <cstdio>#include <string>#include <vector>#include <iomanip>#include <cstring>#include <iostream>#include <algorithm>#define Max 2505#define FI first#define SE second#define ll long long#define PI acos(-1.0)#define inf 0x3fffffff#define LL(x) ( x << 1 )#define bug puts("here")#define PII pair<int,int>#define RR(x) ( x << 1 | 1 )#define mp(a,b) make_pair(a,b)#define mem(a,b) memset(a,b,sizeof(a))#define REP(i,s,t) for( int i = ( s ) ; i <= ( t ) ; ++ i )using namespace std;#define N 111111struct KK{ int e , next ;}ed[N] ;int head[N] , num ;void init(){ mem(head , -1) ;num = 0 ;}void add(int s , int e ){ ed[num].e = e ;ed[num].next = head[s] ; head[s] = num ++ ;}int in[N] , out[N] ;int vis[N] ;int iscr = 0 ;void dfs(int now){ vis[now] ++ ; iscr ++ ;if(iscr >= 1000000)return ;//怕SB数据死循环。 for (int i = head[now] ; ~i ; i = ed[i].next ){ int e = ed[i].e ; dfs(e) ; }}int main() { int a , b ; int mx = 0 , ca = 0 ; while(cin >> a >> b ){ mx = 0 ; if(a == -1 && b == -1)break ; printf("Case %d ", ++ ca) ; if(!a && !b){ puts("is a tree.") ;continue ; } init() ; mem(in , 0) ; mem(out ,0) ;mem(vis ,0) ; mx = max(max(a , b) , mx) ; out[a] ++ , in[b] ++ ; add(a , b) ; vis[a] = vis[b] = 1 ; while(cin >> a >> b , (a + b)){ add(a , b) ; vis[a] = vis[b] = 1 ; mx = max(mx , max(a , b)) ; out[a] ++ , in[b] ++ ; } int root = -1 ;int rootnum = 0 ;bool isok = false ; for (int i = 1 ; i <= mx ; i ++ )if(vis[i] && in[i] == 0)root = i , rootnum ++ ;//根节点和根节点个数 for (int i = 1 ; i <= mx ; i ++ )if(in[i] >= 2)isok = true ;//每个节点的度数 if(root == -1 || rootnum >= 2 || isok)puts("is not a tree.") ; else{ mem(vis ,0) ; dfs(root) ; iscr = false ; bool flag = false ; for (int i = 1 ; i <= mx ; i ++ )if(vis[i] >= 2)flag = true ;//访问到2次或者以上 if(flag)puts("is not a tree.") ; else puts("is a tree.") ; } } return 0 ;}