Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 4958 Accepted Submission(s): 1369
1 #include<string> 2 #include<cstdio> 3 #include<iostream> 4 #include<vector> 5 #include<queue> 6 #include<stack> 7 #include<algorithm> 8 #include<cstring> 9 #include<stdlib.h> 10 #include<string> 11 #include<cmath> 12 using namespace std; 13 #define pb push_back 14 vector<int >p[10010]; 15 int in[10010],n,m,fa[10010]; 16 int ak1[20100],ak2[20100],cnt,check; 17 char ak3[20100]; 18 void init(){ 19 for(int i=0;i<=n;i++) fa[i]=i; 20 memset(in,0,sizeof(in)); 21 for(int i=0;i<=n;i++) p[i].clear(); 22 } 23 int get(int pos){ 24 int tmp=pos,rr; 25 while(fa[tmp]!=tmp) 26 tmp=fa[tmp]; 27 while(fa[pos]!=tmp){ 28 rr=fa[pos]; 29 fa[pos]=tmp; 30 pos=rr; 31 } 32 return tmp; 33 } 34 void tuopu(){ 35 int num=0,p2=0,p3=0; 36 queue<int >ak_47; 37 for(int i=0;i<n;i++) 38 if(in[i]==0&&i==get(i)) ak_47.push(i); 39 while(!ak_47.empty()){ 40 if(ak_47.size()>1) p2=1; 41 int pos=ak_47.front(); 42 num++; 43 for(int i=0;i<p[pos].size();i++){ 44 int to=p[pos][i]; 45 if(--in[to]==0) 46 ak_47.push(to); 47 } 48 ak_47.pop(); 49 } 50 if(num<cnt) p3=1; 51 if(p3) cout<<"CONFLICT"<<endl; 52 else if(p2) cout<<"UNCERTAIN"<<endl; 53 else cout<<"OK"<<endl; 54 } 55 int main(){ 56 while(cin>>n>>m){ 57 init(); 58 int fuck=0; 59 cnt=n; 60 for(int i=1;i<=m;i++){ 61 int a,b; 62 char kk[10]; 63 scanf("%d%s%d",&a,kk,&b); 64 if(kk[0]==‘=‘&&get(a)!=get(b)) fa[get(a)]=get(b),cnt--; 65 ak1[i]=a,ak2[i]=b,ak3[i]=kk[0]; 66 } 67 for(int i=1;i<=m;i++) 68 if(ak3[i]!=‘=‘){ 69 int x=get(ak1[i]),y=get(ak2[i]); 70 if(x==y) fuck=1; 71 if(ak3[i]==‘<‘) in[x]++,p[y].pb(x); 72 else in[y]++,p[x].pb(y); 73 } 74 if(fuck) {cout<<"CONFLICT"<<endl;continue;} 75 tuopu(); 76 } 77 }
原文:http://www.cnblogs.com/ainixu1314/p/3896074.html