najim

1390 - Weight Comparison

May 22nd, 2014
285
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #define SYN ios_base::sync_with_stdio(0);cin.tie(0);
  3. using namespace std;
  4. /***************************************************************************************************************************************/
  5. typedef long long int LLI;
  6. typedef unsigned long long int ULLI;
  7. #define IMAX ((unsigned)1<<31)-1
  8. #define eps 1e-11
  9. #define LIMAX (1LL<<63)-1
  10. #define ULIMAX (1LL<<64)-1
  11. #define UIMAX ((LLI)1<<32)-1
  12. #define MP(X,Y) make_pair(X,Y)
  13.  
  14. #define REP(i,n) for(int i=0;i<n;i++)
  15. #define DREP(i,n) for(int i=n;i>=0;i--)
  16. #define LREP(i,a,b) for(int i=a;i<=b;i++)
  17. #define DLREP(i,a,b) for(int i=a;i>=b;i--)
  18. #define FOR(i,a,b,c) for(int i=a;i<=b;i+=c)
  19.  
  20. #define fill(a,v) memset(a,v,sizeof(a))
  21. #define DEBUG(x) cout << #x << ": " << x << endl;
  22. #define SZ(X) ((int)X.size())
  23. #define all(x) (x).begin(),(x).end()
  24. #define SORT(x) sort(all(x))
  25. #define VI vector<int>
  26. #define VS vector<string>
  27. #define PB push_back
  28. #define REV(a) reverse(all(a))
  29. typedef pair<int, int>PII;
  30. typedef pair<LLI, LLI>PLL;
  31. typedef pair<char, int>PCI;
  32. typedef pair<int, char>PIC;
  33. typedef pair<double, double>PDD;
  34. #define MSI map<string,int>
  35. #define MSLI map<string,LLI>
  36. #define MCI map<char,int>
  37. template<class T> inline T MIN_3(T a, T b, T c)
  38. {
  39.     return min(min(a, b), c);
  40. }
  41. template<class T> inline T MAX_3(T a, T b, T c)
  42. {
  43.     return max(max(a, b), c);
  44. }
  45. #define ACM(x) accumulate(all(x),0);
  46. #define CAP(x,y,z) set_intersection (all(x), all(y), z.begin())
  47. #define CUP(x,y,z) set_union(all(x),all(y),z.begin())
  48. #define DIF(x,y,z) set_difference (all(x),all(y),z.begin());
  49. #define BRPS(n,bit) bitset<bit>(n)
  50. #define DSORT(X)  sort(X.rbegin(), X.rend());
  51. #define read(x) freopen(#x".txt","r",stdin)
  52. #define write(x) freopen(#x".txt","w",stdout)
  53. #define LB(A, x) (lower_bound(all(A), x) - A.begin())//exactly where it starts
  54. #define UB(A, x) (upper_bound(all(A), x) - A.begin())
  55. #define UNQ(x) SORT(x),(x).erase(unique(all(x)),x.end())
  56.  
  57. template<class T> inline T BIGMOD(T n, T m, T mod)
  58. {
  59.     LLI ans = 1;
  60.     LLI k = n;
  61.     while(m)
  62.     {
  63.         if(m & 1)
  64.         {
  65.             ans *= k;
  66.             if(ans>mod) ans %= mod;
  67.         }
  68.         k *= k;
  69.         if(k>mod) k %= mod;
  70.         m >>= 1;
  71.     }
  72.     return ans;
  73. }
  74.  
  75.  
  76. inline int DBLCMP(double a, double b)
  77. {
  78.     if(fabs(a - b) <= eps) return 0;
  79.     if(a < b) return -1;
  80.     return 1;
  81. }
  82. template<class T> inline T sqr(T x)
  83. {
  84.     return x*x;
  85. }
  86. template<class T> inline int countbit(T n)
  87. {
  88.     return (n == 0) ? 0 : (1 + countbit(n&(n - 1)));
  89. }
  90. template<class T> inline T euclide(T a, T b, T &x, T &y)
  91. {
  92.     if (a < 0)
  93.     {
  94.         T d = euclide(-a, b, x, y);
  95.         x = -x;
  96.         return d;
  97.     }
  98.     if (b < 0)
  99.     {
  100.         T d = euclide(a, -b, x, y);
  101.         y = -y;
  102.         return d;
  103.     }
  104.     if (b == 0)
  105.     {
  106.         x = 1;
  107.         y = 0;
  108.         return a;
  109.     }
  110.     else
  111.     {
  112.         T d = euclide(b, a % b, x, y);
  113.         T t = x;
  114.         x = y;
  115.         y = t - (a / b) * y;
  116.         return d;
  117.     }
  118. }
  119. template<class T> string toString(T n)
  120. {
  121.     ostringstream ost;
  122.     ost << n;
  123.     ost.flush();
  124.     return ost.str();
  125. }
  126. template<class T> string toBinary(T n)
  127. {
  128.     string ret="";
  129.     while(n)
  130.     {
  131.         if(n%2==1)ret+='1';
  132.         else ret+='0';
  133.         n>>=1;
  134.     }
  135.     reverse(ret.begin(),ret.end());
  136.     return ret;
  137. }
  138. void combination(int n,vector< vector<int> > &ret)
  139. {
  140.     ret.resize(n+1, vector<int>(n+1, 0));
  141.     for(int i=1; i<=n; i++)
  142.     {
  143.         ret[i][0]=ret[i][i]=1;
  144.         for(int j=1; j<i; j++)
  145.         {
  146.             ret[i][j]=ret[i-1][j]+ret[i-1][j-1];
  147.         }
  148.     }
  149. }
  150. int toInt(string s)
  151. {
  152.     int r = 0;
  153.     istringstream sin(s);
  154.     sin >> r;
  155.     return r;
  156. }
  157. LLI toLInt(string s)
  158. {
  159.     LLI r = 0;
  160.     istringstream sin(s);
  161.     sin >> r;
  162.     return r;
  163. }
  164. double toDouble(string s)
  165. {
  166.     double r = 0;
  167.     istringstream sin(s);
  168.     sin >> r;
  169.     return r;
  170. }
  171. vector<string> parse(string temp)
  172. {
  173.     vector<string> ans;
  174.     ans.clear();
  175.     string s;
  176.     istringstream iss(temp);
  177.     while (iss >> s)ans.PB(s);
  178.     return ans;
  179. }
  180. template<class T> inline T gcd(T a, T b)
  181. {
  182.     if (a < 0)return gcd(-a, b);
  183.     if (b < 0)return gcd(a, -b);
  184.     return (b == 0) ? a : gcd(b, a % b);
  185. }
  186. template<class T> inline T lcm(T a, T b)
  187. {
  188.     if (a < 0)return lcm(-a, b);
  189.     if (b < 0)return lcm(a, -b);
  190.     return a*(b / gcd(a, b));
  191. }
  192. template<class T> inline T power(T b, T p)
  193. {
  194.     if (p < 0)return -1;
  195.     if (b <= 0)return -2;
  196.     if (!p)return 1;
  197.     return b*power(b, p - 1);
  198. }
  199. #define fst first
  200. #define snd second
  201. //istringstream(temp) >> data >> value >> stamp;
  202. //mod1 = 1000000007, mod2 = 1000000009;
  203. //.016-.040-.900-2.48
  204. /***************************************************************************************************************************************/
  205. int N,E;
  206. vector<int>adj[5009];
  207. bool vis[5009];
  208. vector<int>topo;
  209. vector<PII>Edges;
  210. int color[5009];
  211. set<PII>del;
  212. vector<PII>res;
  213.  
  214. void ini()
  215. {
  216.     for(int i=0;i<=5002;i++)adj[i].clear();
  217.     fill(vis,0);
  218.     fill(color,0);
  219.     topo.clear();
  220.     Edges.clear();
  221.     del.clear();
  222.     res.clear();
  223.  
  224. }
  225. void topoSort(int cn)
  226. {
  227.     vis[cn]=true;
  228.     REP(i,adj[cn].size())
  229.     {
  230.         if(!vis[adj[cn][i]])topoSort(adj[cn][i]);
  231.     }
  232.     topo.PB(cn);
  233. }
  234.  
  235. void dfs(int cn)
  236. {
  237.     color[cn]=1;
  238.     int now;
  239.     REP(i,adj[cn].size())
  240.     {
  241.         now=adj[cn][i];
  242.         if(color[now]==2)
  243.         {
  244.             del.insert(MP(cn,now));
  245.         }
  246.         else
  247.         {
  248.             dfs(now);
  249.         }
  250.     }
  251.     color[cn]=2;
  252.     return ;
  253. }
  254.  
  255.  
  256. int main()
  257. {
  258.     //SYN
  259.     //read();
  260.     //write();
  261.     int kase,ks=0,a,b;
  262.     scanf("%d",&kase);
  263.     while(kase--)
  264.     {
  265.         scanf("%d %d",&N,&E);
  266.         REP(i,E)
  267.         {
  268.             scanf("%d %d",&a,&b);
  269.             adj[a].PB(b);
  270.             Edges.PB(MP(a,b));
  271.         }
  272.         //topoSort(1);
  273.         for(int i=1; i<=N; i++)
  274.         {
  275.             if(!vis[i]) topoSort(i);
  276.         }
  277.         for(int i=topo.size()-1;i>=0;i--)
  278.         {
  279.             if(color[topo[i]]==0)
  280.             {
  281.                 dfs(topo[i]);
  282.             }
  283.         }
  284.         for(int i=0;i<E;i++)
  285.         {
  286.             a=Edges[i].fst;
  287.             b=Edges[i].snd;
  288.             if(del.find(MP(a,b))!=del.end());
  289.             else res.PB(MP(a,b));
  290.         }
  291.         SORT(res);
  292.         printf("Case %d: ",++ks);
  293.         cout << res.size() << endl;
  294.         REP(i,res.size())
  295.         {
  296.             printf("%d %d\n",res[i].fst,res[i].snd);
  297.         }
  298.         ini();
  299.     }
  300.     return 0;
  301. }
RAW Paste Data