(以“分类:并查集 ==摘要== {{信息题|Mr. Kitayuta's Colorful Graph|http://acm.hust.edu.cn/vjudge/contest/view.action?cid{{=}}70536#problem/H|1|100|time=2015-0...”为内容创建页面) |
小 (→题解: 表达) |
||
第7行: | 第7行: | ||
图,边有颜色,问任意两点之间直接或间接连边的颜色(要求都是同色)。 | 图,边有颜色,问任意两点之间直接或间接连边的颜色(要求都是同色)。 | ||
==题解== | ==题解== | ||
− | * | + | *并查集,不同颜色用数组分开就好惹。 |
+ | |||
==代码== | ==代码== | ||
{{折叠|505B.cpp代码已折叠 | {{折叠|505B.cpp代码已折叠 |
题目链接 | 难度等级 | 完成状态 | 完成分数 | 最后编辑时间 | 需要注意 |
---|---|---|---|---|---|
Mr. Kitayuta's Colorful Graph | ★☆☆☆☆ | 答案正确 | 100 | 2015-02-23 14:56:25 | 无 |
图,边有颜色,问任意两点之间直接或间接连边的颜色(要求都是同色)。
505B.cpp代码已折叠
展开折叠内容
|
---|
#include <iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<cstdlib> #include<climits> #include<queue> #include<vector> #define f(i,n) for(int i=1;i<=n;++i) #define fi(i,t,n)for(int i=t;i<=n;++i) #define fd(i,n) for(int i=n;i>=1;--i) #define fdi(i,t,n) for(int i=n;i>=t;--i) #define foreach(i,s) for(typeof(s.begin()) i=s.begin();i!=s.end();++i) #define rforeach(i,s) for(typeof(s.rbegin()) i=s.rbegin();i!=s.rend();++i) #define si(n) scanf("%d",&n) #define dsi(n) int n;scanf("%d",&n) #define llu unsigned long long #define lld long long #define ci const int & using namespace std; int f[1000][1000]={},maxC=0; int getF(ci x,ci color) { return (f[color][x]==x)?x:f[color][x]=getF(f[color][x],color); } void link(ci a,ci b,ci color) { maxC=max(color,maxC); f[color][getF(a,color)]=getF(b,color); } bool isLink(ci a,ci b,ci color) { return getF(a,color)==getF(b,color); } int getColor(ci a,ci b) { int ret=0; for(int i=1;i<=maxC;++i) if(isLink(a,b,i)) ++ret; return ret; } int main() { dsi(n); f(i,101)f(j,101)f[i][j]=j; dsi(m); f(i,m) { dsi(a);dsi(b);dsi(c); link(a,b,c); } si(m); f(i,m) { dsi(a);dsi(b); printf("%d\n",getColor(a,b)); } } |