# 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());
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;
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. {
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;
229.     {
231.     }
232.     topo.PB(cn);
233. }
234.
235. void dfs(int cn)
236. {
237.     color[cn]=1;
238.     int now;
240.     {
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
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);
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