HDU 4751 Divide Groups

题目链接

比赛时候,建图建错了。大体算法想到了,不过很多细节都没想好。

 #include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int flag[];
int p[][];
int o[][];
int n,z;
void dfs(int x,int step)
{
int i;
if(z) return ;
for(i = ; i <= n; i ++)
{
if(i == x) continue;
if(o[x][i]&&!flag[i])
{
flag[i] = step% + ;
dfs(i,step+);
}
else if(o[x][i]&&flag[i])
{
if(flag[i] != step% + )
{
z = ;
return ;
}
}
}
return ;
}
int main()
{
int i,j;
while(scanf("%d",&n)!=EOF)
{
memset(flag,,sizeof(flag));
memset(p,,sizeof(p));
memset(o,,sizeof(o));
for(i = ; i <= n; i ++)
{
for(;;)
{
scanf("%d",&j);
if(j == ) break;
p[i][j] = ;
}
}
for(i = ;i <= n;i ++)
{
for(j = ;j <= n;j ++)
{
if(!p[i][j]||!p[j][i])
o[i][j] = o[j][i] = ;
}
}
z = ;
for(i = ; i <= n; i ++)
{
if(!flag[i])
{
flag[i] = ;
dfs(i,);
}
}
if(z)
printf("NO\n");
else
printf("YES\n");
}
return ;
}
上一篇:zigbee学习之路(十四):基于协议栈的无线数据传输


下一篇:【转】为什么 MQTT 是最适合物联网的网络协议