首页 > 代码库 > hdu 3172 Virtual Friends (并查集 + 字典树)
hdu 3172 Virtual Friends (并查集 + 字典树)
题目:
链接:点击打开链接
题意:
输入n,给出n行数据,每行有两个字符串,输出关系网络中朋友的个数,n行。
思路:
代码:
#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> using namespace std; const int N = 22; const int M = 200020; struct node { int c; node *child[52]; node() { c = 0; for(int i=0; i<52; i++) child[i] = NULL; } }*root1; int n; int cnt; int root[M]; char stra[N],strb[N]; int insertTrie(char s[])//字典树功能:将名字映射成代表该名字的一个整数 { node *p = root1; int len = strlen(s); for(int k,i=0; i<len; i++,p=p->child[k]) { if(s[i] >= 'a' && s[i] <= 'z') k = s[i] - 'a'; else k = s[i] - 'A' + 26; if(!p->child[k]) p->child[k] = new node(); } if(p->c) return p->c; return p->c = ++cnt; } void init() { for(int i=0; i<M; i++) root[i] = -1; } int findset(int x) { int r; for(r=x; root[r]>0; r=root[r]); while(r != x) { int temp = root[x]; root[x] = r; x = temp; } return r; } int mergeset(int r1,int r2) { int temp = root[r1] + root[r2]; if(root[r1] > root[r2]) { root[r1] = r2; root[r2] = temp; } else { root[r2] = r1; root[r1] = temp; } return temp; } void dealTrie(node *p) { for(int i=0; i<52; i++) { if(p->child[i]) dealTrie(p->child[i]); } delete p; p = NULL; } int main() { //freopen("input.txt","r",stdin); int t; while(scanf("%d",&t) != EOF) { while(t--) { scanf("%d",&n); getchar(); cnt = 0; init(); root1 = new node(); for(int i=0; i<n; i++) { scanf("%s%s",stra,strb); int x = insertTrie(stra); int y = insertTrie(strb); int fx = findset(x); int fy = findset(y); if(fx != fy) printf("%d\n",abs(mergeset(fx,fy))); else printf("%d\n",abs(root[fx])); } dealTrie(root1); } } return 0; }
------------------------------------------------------
战斗,从不退缩;奋斗,永不停歇~~~~~~~~~~~~
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。