题意:
有一群人,有的人认识某些人(认识的关系是单向的)...现在需要将这些人分成两个部分,而一个好的部分为以下定义:
1、一个部分的人数多少与好坏无关
2、一个部分中所有的人都是两两认识的
问能否将所有的人成功划分成两个好的部分.
题解:
因为关系牵扯错纵复杂,直接DFS就好..自然的会有很多剪枝...
Program:
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<queue> #include<vector> #include<cstdlib> #include<stack> #include<map> #define MAXN 10005 #define MAXM 1000505 #define ll long long #define eps 1e-10 using namespace std; bool f[105][105]; int b[105]; bool judge(int x,int n) { int i; if (x>n) return true; for (i=1;i<=n;i++) if (b[i]==1 && (!f[i][x] || !f[x][i])) break; if (i<=n) { for (i=1;i<=n;i++) if (b[i]==2 && (!f[i][x] || !f[x][i])) break; if (i<=n) return false; b[x]=2; if (judge(x+1,n)) return true; b[x]=0; }else { for (i=1;i<=n;i++) if (b[i]==2 && (!f[i][x] || !f[x][i])) break; if (i<=n) { b[x]=1; if (judge(x+1,n)) return true; b[x]=0; }else { b[x]=1; if (judge(x+1,n)) return true; b[x]=2; if (judge(x+1,n)) return true; b[x]=0; } } return false; } int main() { int n,i,j,x; while(~scanf("%d",&n)) { memset(f,false,sizeof(f)); for (i=1;i<=n;i++) while (scanf("%d",&x) && x) f[i][x]=true; memset(b,0,sizeof(b)); if (!judge(1,n)) printf("NO\n"); else printf("YES\n"); } return 0; }