poj 1470 Closest Common Ancestors

点击打开链接poj 1470

思路：LCA+Tarjan离线算法

分析：
1 处理输入的时候全部用scanf，不然会WA。注意掌握scanf的使用，scanf的灵活之处
2 因为有多次询问，所以要开个ans数组记录公共祖先的次数
3 有关字符串的处理： 1 空白字符会使scanf在读入的时候略去其中的一个或多个空白字符 。 2 getchar()使用来读入一个字符，所以可以单独处理一个字符。

代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
#define MAXN 10010

int n , m;
int father[MAXN];
int ancestor[MAXN];
int first[MAXN];
int next[MAXN];
int vis[MAXN];
int ans[MAXN];
int indegree[MAXN];
vector<int>v[MAXN];

/*初始化*/
void init(){
   for(int i = 1 ; i <= n ; i++){
      father[i] = i;
      v[i].clear();
   }
   memset(ancestor , -1, sizeof(ancestor));
   memset(first , -1 , sizeof(first));
   memset(next , -1 , sizeof(next));
   memset(vis , 0 , sizeof(vis));
   memset(ans , 0 , sizeof(ans));
   memset(indegree , 0 , sizeof(indegree));
}

/*并查集的查找*/
int find_Set(int x){
   if(x != father[x])
     father[x] = find_Set(father[x]);
   return father[x];
}

/*并查集的合并*/
void union_Set(int x , int y){
   int root_x = find_Set(x);
   int root_y = find_Set(y);
   father[root_x] = root_y;
}

/*Tarjan算法*/
void LCA(int u){
    ancestor[u] = u;
    for(int i = first[u] ; i != -1 ; i = next[i]){
       LCA(i);
       union_Set(i , u);
       ancestor[find_Set(i)] = u; /*这里是i的根节点不是i*/
    }
    vis[u] = 1;
    for(int i = 0 ; i < v[u].size() ; i++){
       if(vis[v[u][i]])
         ans[father[find_Set(v[u][i])]]++;/*这里要加加*/
    }
}

int main(){
    char c , ch[MAXN];
    int a , b , t;
    while(scanf("%d%*c" , &n) != EOF){
       init();/*初始化*/
       for(int i = 0 ; i < n ; i++){
          scanf("%d:(%d)" , &a , &t);
          for(int j = 0 ; j < t ; j++){
             scanf("%d" , &b);/*直接scnaf("%d",&b)即可，因为scanf会过滤空白字符*/
             next[b] = first[a];
             first[a] = b;
             indegree[b]++;/*入度加1*/
          }
       }
       scanf("%d%*c" , &m);
       for(int i = 0 ; i < m ; i++){
          while(getchar() != '(');/*读掉空格，知道遇到左括号*/
          scanf("%d %d)" , &a, &b);/*读入值*/
          v[a].push_back(b);/*插入vector容器*/
          v[b].push_back(a);
       }
       for(int i = 1 ; i <= n ; i++){
          if(!indegree[i]){
             LCA(i);
             break;
          }
       }
       for(int i = 1 ; i <= n ; i++){/*输出*/
          if(ans[i])
            printf("%d:%d\n" , i , ans[i]);
       }
    }
    return 0;
}