题意：n个人，给出每个人认识的人的信息。问能否将这些人分成两组，保证每组至少1个人，并且两两互相认识。
思路：首先是反向建图。由于要求同组内两个人互相认识，那么两个人u,v，只要u不认识v或者v不认识有一个满足，就连接双向边u,v，表示u,v不能分到同一组。
由于图反向以后不保证联通，因此求补图以后可能会得到几个联通分量。
而合法的条件是，每个联通分量都合法。
不合法的条件是，只要由一个联通分量不合法。
以及：之前把交叉染色部分写错了。上道题可以通过纯粹是因为数据水。。？
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 |
/* *********************************************** Author :111qqz Created Time :2016年09月01日 星期四 01时13分04秒 File Name :code/hdu/4751.cpp ************************************************ */ #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> #include <string> #include <cmath> #include <cstdlib> #include <ctime> #define fst first #define sec second #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define ms(a,x) memset(a,x,sizeof(a)) typedef long long LL; #define pi pair < int ,int > #define MP make_pair using namespace std; const double eps = 1E-8; const int dx4[4]={1,0,0,-1}; const int dy4[4]={0,-1,1,0}; const int inf = 0x3f3f3f3f; const int N=205; int n; bool know[N][N]; int col[N]; vector<int>edge[N]; bool dfs( int u,int x) { col[u] = x; int siz = edge[u].size(); for ( int i = 0 ; i < siz; i++) { int v = edge[u][i]; if (col[v]==x) return false; if (col[v]==1-x) continue; if (!dfs(v,1-x)) return false; } return true; } bool ok() { for ( int i = 1 ; i <= n ; i++) //每个联通分量都合法才合法。 if (col[i]==-1) if (!dfs(i,0)) return false; return true; } int main() { #ifndef ONLINE_JUDGE freopen("code/in.txt","r",stdin); #endif while (~scanf("%d",&n)) { ms(col,-1); for ( int i = 0 ; i <= n ;i++) edge[i].clear(); ms(know,false); for ( int i = 1 ; i <= n ; i++) { int x; while (~scanf("%d",&x)&&x!=0) { know[i][x] = true; } } for ( int i = 1 ; i <= n ; i++) for ( int j = i+1 ; j <= n ; j++) { if (know[i][j]&&know[j][i]) continue; // cout<<"i:"<<i<<" j:"<<j<<endl; edge[i].push_back(j); edge[j].push_back(i); } if (ok()) puts("YES"); else puts("NO"); } #ifndef ONLINE_JUDGE fclose(stdin); #endif return 0; } |
说点什么
您将是第一位评论人！