点击打开链接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;
}
分享到:
相关推荐
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
动态规划 poj Common Subsequence c++ cpp文件
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
poj分类poj分类poj分类poj分类
北大POJ1159-Palindrome 解题报告+AC代码
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
POJ1503解答 POJ1503解答,正确答案(已通过POJ)
北大POJ2002-Squares 解题报告+AC代码
POJ1048,加强版的约瑟夫问题 难度中等
POJ1083的代码,POJ1083的代码,POJ1083的代码
poj 百练 题目分类 poj 百练 题目分类
poj 1001答案
POJ2968代码有用,欢迎下载,POJ代码
poj 1440解题报告 poj 1440解题报告 poj 1440解题报告 poj 1440解题报告
poj 3083解题报告poj 3083解题报告poj 3083解题报告poj 3083解题报告