首页 > 代码库 > POJ 1703 Find them, Catch them
POJ 1703 Find them, Catch them
题目链接:http://poj.org/problem?id=1703
思路:种类并查集。 并设置一个opp数组,opp[i]代表与i相对立的。
代码:
#include <iostream>#include <cstdio>using namespace std;int c,d;int t1,t2;int opp[100005];int f[100005];int getf(int x){ if(f[x] == x) { return x; } return f[x] = getf(f[x]);}void merge(int x,int y){ int a = getf(x); int b = getf(y); if(a!=b) { f[b] = a; }}void init(){ for(int i=1;i<=t1;i++) { f[i] = i; opp[i] = 0; }}int main(){ int n; scanf("%d",&n); getchar(); char str[10]; while(n--) { scanf("%d %d",&t1,&t2); getchar(); init(); for(int i=1;i<=t2;i++) { scanf("%s %d %d",str,&c,&d); getchar(); if(str[0]==‘D‘) { if(opp[c]==0&&opp[d]==0) { opp[c] = d; opp[d] = c; } else if(opp[c]==0) { opp[c] = d; merge(opp[d],c); } else if(opp[d]==0) { opp[d] = c; merge(opp[c],d); } else { merge(opp[c],d); merge(opp[d],c); } } else { if(t1==2) { printf("In different gangs.\n"); continue; } int temp1 = getf(c); int temp2 = getf(d); if(temp1==temp2) { printf("In the same gang.\n"); } else if(temp1 == getf(opp[d])) { printf("In different gangs.\n"); } else { printf("Not sure yet.\n"); } } } } return 0;}
POJ 1703 Find them, Catch them
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。