思路: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; }