05-ツリー8 File Transfer【検索集】
1019 ワード
タイトル:File Transfer
入力形式は3種類あります.「I a b」代表:a、bは接続可能です.「C a b」代表:a、bは接続可能ですか?「S」は終了です.出力クエリは接続可能です.
考え方:基本的にまとめて操作します.
コード:
入力形式は3種類あります.「I a b」代表:a、bは接続可能です.「C a b」代表:a、bは接続可能ですか?「S」は終了です.出力クエリは接続可能です.
考え方:基本的にまとめて操作します.
コード:
#include
#include
const int maxn = 10005;
int f[maxn];
void init(int n){
for(int i=0;i<=n;i++) f[i] = i;
}
inline int find(int v){
if(f[v] != v) f[v] = find(f[v]);
return f[v];
}
inline void merge(int u,int v){
int tu = find(u);
int tv = find(v);
if(tu != tv) f[tv] = tu;
}
int main(){
int n,u,v;
char s[5];
while(scanf("%d",&n)!=EOF){
init(n);
while(scanf("%s",s) && s[0] != 'S'){
scanf("%d%d",&u,&v);
if(s[0] == 'I') merge(u,v);
else{
if(find(u) == find(v)) printf("yes
");
else printf("no
");
}
}
int cnt = 0;
for(int i=1;i<=n;i++){
if(f[i] == i) cnt++;
}
if(cnt > 1) printf("There are %d components.
",cnt);
else printf("The network is connected.
");
}
}