fork download
copy 
  1. /**********************************************************************************/  
  2. /*  Problem: b017 "B.家長會問題" from 2007 校內初選                               */  
  3. /*  Language: C++                                                                 */  
  4. /*  Result: NA (18 / 27) on ZeroJudge                                             */  
  5. /*  Author: ForTest at 2014-03-25 13:46:24                                        */  
  6. /**********************************************************************************/  
  7.  
  8. #include <iostream>  
  9. #include <cstdio>  
  10. #include <cstring>  
  11. #include <vector>  
  12. #include <algorithm>  
  13. #include <map>  
  14. #include <queue>  
  15. #include <sstream>  
  16.  
  17. using namespace std;  
  18.  
  19. #define F(a,b) for(int a=0;a<b;++a)  
  20. typedef long long LL;  
  21.  
  22. const int mv=1000;int cv;  
  23. int n,m;  
  24. int v[mv],scc[mv];  
  25. vector<int>e[mv],be[mv],topo,ans;  
  26.  
  27. int Not(int a){return -a;}  
  28. void Add(int a,int b){  
  29.     e[a].push_back(b);  
  30.     be[b].push_back(a);  
  31. }  
  32.  
  33. void Dfs(vector<int> *E,int x,int tag = -1){  
  34.     if(v[x])return;  
  35.     v[x] = 1;   scc[x] = tag;  
  36.     F(i,E[x].size())  
  37.         Dfs(E, E[x][i], tag);  
  38.     if(E == e)  
  39.         topo.push_back(x);  
  40. }  
  41. void Kos(){  
  42.     memset(v,0,sizeof v);  
  43.     for(int i=n+1;i<cv;++i) Dfs(e,i);  
  44.     for(int i=0;i<n;++i) Dfs(e,i);  
  45.     memset(v,0,sizeof v);  
  46.     int cnt = 0;  
  47.     for(int i=topo.size()-1;i>=0;--i)  
  48.         Dfs(be,topo[i],cnt++);  
  49. }  
  50.  
  51. bool Output(){  
  52.     for(int i=1+n;i<cv;++i) if(scc[i] == scc[n*2-i]){  
  53.         puts("0"); return 0;}  
  54.     printf("%d\n",n);  
  55.     for(int i=1+n;i<cv;++i)  
  56.         printf( (scc[i] > scc[n*2-i]) ?  
  57.                 "+" : "-");  
  58.     puts("");  
  59.     return 1;  
  60. }  
  61.  
  62. int main(){  
  63.     scanf("%d%d",&n,&m);  
  64.     cv = n*2 + 1;  
  65.     F(i,m){  
  66.         int a,b;  
  67.         scanf("%d%d",&a,&b);  
  68.         Add(Not(a)+n,b+n);  
  69.         Add(Not(b)+n,a+n);  
  70.     }  
  71.     Kos();  
  72.     Output();  
  73.     return 0;  
  74. }
Success #stdin #stdout 0s 3332KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/VdWqVn
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!