[ACM ] 10505
這題自己想了很久解不出來，
只好來求救
這題應該是用Disjoint sets來解，
但是我遇到兩個困難
第一個就是 對於那些沒有朋友或敵人的人
沒有辦法加入set裡面
第二個就是 像是sample input第三個
三個人都同時互為敵友關係的矛盾情形無法判斷
不知道有沒有人能提示一下或是給一些想法別的解法
我只能寫到基本的 謝謝
#include<stdio.h>
#include<string.h>
#define MAX 201
int num[MAX];
int enemy[MAX];
int w[MAX];
int find(int x)
{
while(x != w[x])
x = w[x];
return x;
}
void unite(int x , int y)
{
x = find(x);
y = find(y);
if(x == y || !x || !y)
return;
num[y] += num[x];
num[x] = 0;
w[x] = y;
}
void set_enemy(int x , int y)
{
x = find(x);
y = find(y);
if(x == y)
return;
unite(enemy[x],y);
unite(enemy[y],x);
enemy[x] = y;
enemy[y] = x;
}
int main()
{
int m,n,i,p,j,e;
scanf("%d",&m);
while(m--)
{
scanf("%d",&n);
for(i=1;i<=n;i++)
{
enemy[i] = 0;
w[i] = i;
num[i] = 0;
}
for(i=1;i<=n;i++)
{
scanf("%d",&p);
for(j=0;j<p;j++)
{
scanf("%d",&e);
set_enemy(i,e);
}
}
}
return 0;
}
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 218.173.138.201
→
08/26 23:44, , 1F
08/26 23:44, 1F
C_and_CPP 近期熱門文章
PTT數位生活區 即時熱門文章