ll T; while(~scanf("%d",&T)){ while(T--) {
= = ...
思路：
用秩合並，看了題解才發現 if(fx == fy)要輸出當前集合的秩而不是0。。。
#include #include #include #include #include #include #include #include #include #include using namespace std; #define mod 1000000007 #define ll int #define N 100100 ll r[N], f[N]; ll find(ll x){return x==f[x]?x:f[x] = find(f[x]);} ll Union(ll x, ll y){ ll fx = find(x), fy = find(y); if(fx==fy)return r[fx]; if(r[fx]>r[fy]) swap(fx,fy); f[fx] = fy; r[fy] += r[fx]; return r[fy]; } ll n; void init(){ for(ll i = 0; i < N; i++) r[i] = 1; for(ll i = 0; i < N; i++) f[i] = i; } #define Word_Len 50500 #define Sigma_size 95 struct Trie{ ll ch[Word_Len][Sigma_size]; //Word_Len是字典樹的節點數 若都是小寫字母Sigma_size=26 ll Have_word[Word_Len]; //這個節點下有幾個單詞 ll val[Word_Len]; // 這個節點附帶的信息，初始化為0表示這個節點不存在單詞，所以節點帶的信息必須!=0 ll sz ; //當前節點數 ll pre[Word_Len]; char he[Word_Len]; ll Newnode(){memset(ch[sz], 0, sizeof(ch[sz])); val[sz]=Have_word[sz]=0; return sz++;} void init() //初始化字典樹 { sz = 0; Newnode();}//初始化 ll idx(char c){return c-32;} //字符串編號 ll insert(char *s){ //把v數字加給 s單詞最後一個字母 ll u = 0, len = strlen(s); for(ll i = 0; i < len; i++){ ll c = idx(s[i]); if(!ch[u][c]) //節點不存在就新建後附加 { he[sz] = s[i]; val[sz] = val[u]+1; pre[sz] = u; ch[u][c] = Newnode(); } u = ch[u][c]; Have_word[u]++; } //現在的u就是這個單詞的最後一個位置 return u; } ll find_word(char *s){ ll u = 0, len = strlen(s); for(ll i = 0; i < len; i++){ ll c = idx(s[i]); if(!ch[u][c])return 0; //節點不存在 u = ch[u][c]; } return Have_word[u]; } void Have_name(char *s, ll now){ ll len = val[now]; s[len--] = 0; ll cc = now; while(cc) { s[len--] = he[cc]; cc = pre[cc]; } } }; Trie ac; char a[1005], b[1005]; int main(){ ll T; while(~scanf("%d",&T)){ while(T--) { cin>>n; init(); ac.init(); while(n--) { cin>>a>>b; ll u, v; u = ac.insert(a); v = ac.insert(b); cout<
字符串函數---strcpy()與strncpy()詳解及實
C++進階學習——單向鏈表的實現 示例代碼如下：
本文轉載自：http://www.zaojiahua.
C++那些細節--typedef關鍵字 一
BZOJ 1227 [SDOI2009] 虔誠的墓主人 離線
題意：有一個周長為10000的圓上等距分布著n個雕塑，
