欧美成人亚洲成人日韩成人,国产欧美一区二区三区久久,欧美视频亚洲视频

pku 1703

2009年7月13日星期一

題目鏈接：PKU 1703 并查集的拓展

分類：并查集的拓展

題目分析與算法模型
類似于2492，算法基本一樣，細(xì)節(jié)處稍作修改即可，呵呵

Code:

1

#include<stdio.h>
2

#define max 100005
3

int i,j,parent[max],kind[max],t,n,m,a,b;
5

char kk;
6

void init(int n)
8

{
9

for(j=1;j<=n;j++)
10

{
11

parent[j]=-1;
12

kind[j]=0;
13

}
14

}
15

int find(int x)
16

{
17

int t=parent[x];
18

if(t<0)return x;
19

parent[x]=find(t);
20

kind[x]=(kind[x]+kind[t])%2;
21

return parent[x];
22

}
23

void Union(int x,int y,char k)
24

{
25

int root1=find(x),root2=find(y);
26

if(k=='A')
27

{
28

if(root1!=root2)printf("Not sure yet.\n");
29

else
30

{
31

if(kind[x]==kind[y])printf("In the same gang.\n");
32

else printf("In different gangs.\n");
33

}
34

}
35

else
36

{
37

if(root1!=root2)
38

{
39

parent[root2]+=parent[root1];
40

parent[root1]=root2;
41

kind[root1]=(kind[y]+kind[x]+1)%2;
42

}
43

}
44

}
46

int main()
47

{
48

scanf("%d",&t);
49

while(t--)
50

{
51

scanf("%d%d",&n,&m);
52

init(n);
53

for(i=0;i<m;i++)
54

{
55

scanf(" %c%d%d",&kk,&a,&b);
56

Union(a,b,kk);
57

}
58

}
59

return 0;
60

}
61

posted on 2009-07-13 00:27 蝸牛也Coding 閱讀(1085) 評(píng)論(2) 編輯收藏引用

評(píng)論

# re: pku 1703 2009-07-13 11:57 99讀書人

不錯(cuò)！！回復(fù) 更多評(píng)論

# re: pku 1703[未登錄](méi) 2009-08-24 17:51 abilitytao

parent[root2]+=parent[root1];
這句有點(diǎn)多余其實(shí)可以刪掉回復(fù) 更多評(píng)論

刷新評(píng)論列表

只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。
【推薦】100%開(kāi)源！大型工業(yè)跨平臺(tái)軟件C++源碼提供，建模，組態(tài)！



網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問(wèn) Chat2DB 管理

# re: pku 1703 2009-07-13 11:57 99讀書人

# re: pku 1703[未登錄](méi) 2009-08-24 17:51 abilitytao

pku 1703

評(píng)論

導(dǎo)航

統(tǒng)計(jì)

常用鏈接

留言簿(8)

隨筆檔案(78)

搜索

積分與排名

最新評(píng)論

閱讀排行榜

評(píng)論排行榜