（以“分类:并查集 ==摘要== {{信息题|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));
}
}
|
CloudLunar