TIOJ 1209 - 圖論 之 二分圖測試

http://tioj.infor.org/problems/1209

就 裸裸的走下去

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

#include<vector> #include<cstdio> #include<cstring> using namespace std; int n,m,i,zz,zzz,t; char c; vector<int> con[40005]; short gone[40005]; bool jizz; int dfs(int now,int type){ gone[now]=type; for(int j=0;j<con[now].size();j++){ if(gone[con[now][j]]!=0){ if(gone[con[now][j]]==type){ return -1; } } else{ if(dfs(con[now][j],-type)==-1){ return -1; } } } return 1; } inline int rit(){ t=0; do{ c=getchar_unlocked(); }while(c<'0'||c>'9'); do{ t=t*10+c-'0'; c=getchar_unlocked(); }while(c>='0'&&c<='9'); return t; } int main(){ while(scanf("%d%d",&n,&m)!=EOF){ if(n==0 && m==0) break; for(i=0;i<n+3;i++){ con[i].clear(); } memset(gone,0,sizeof(gone)); jizz=0; for(i=0;i<m;i++){ zz=rit(),zzz=rit(); con[zz].push_back(zzz); con[zzz].push_back(zz); } for(i=1;i<=n;i++){ if(!gone[i]){ if(dfs(1,111)==-1){ printf("No\n"); jizz=1; break; } } } if(!jizz){ printf("Yes\n"); } } }