Advertisement
Guest User

Untitled

a guest
Jun 22nd, 2017
54
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.69 KB | None | 0 0
  1. #include <cstdio>
  2. #include <map>
  3. #include <set>
  4. #include <sstream>
  5. #include <string>
  6. #include <iostream>
  7. #include <utility>
  8. #include <queue>
  9. #include <cmath>
  10. using namespace std;
  11. #define forn(i,n) for(int i=0;i<(n);++i)
  12. #define fornr(i,n) for(int i=(n)-1;i>=0;--i)
  13. #define forv(i,v) forn(i,(int)v.size())
  14. #define forvr(i,v) fornr(i,(int)v.size())
  15. #define mp make_pair
  16. #define pb push_back
  17. #define lng long long
  18. #define SQ(a) ((a)*(a))
  19. #define eps 1e-8
  20. #define VI vector<int>
  21.  
  22.  
  23. bool can[1000][1000];
  24. vector<int> grav[1000+100];
  25. bool was[1000+100];
  26. int s;
  27. int a[30000];
  28. int b[30000];
  29.  
  30. void dfs(int v)
  31. {
  32. was[v]=true;
  33. can[s][v]=true;
  34. forv(i,grav[v])
  35. {
  36. if (!was[grav[v][i]])
  37. {
  38. dfs(grav[v][i]);
  39. }
  40. }
  41. }
  42.  
  43. int val[30000];
  44.  
  45.  
  46. int main(int argc, char *argv[])
  47. {
  48. #ifdef __qwe__
  49. freopen("input.txt", "r", stdin);
  50. freopen("output.txt", "w", stdout);
  51. #endif
  52. int n, m;
  53. cin >> n >> m;
  54. forn(i,m)
  55. {
  56. int u, v;
  57. scanf("%d%d", &u, &v);
  58. --u;--v;
  59. grav[u].pb(v);
  60. a[i]=u;
  61. b[i]=v;
  62. }
  63.  
  64.  
  65. forn(i,n)
  66. {
  67. s = i;
  68. memset(was,0,sizeof(was));
  69. dfs(s);
  70. }
  71.  
  72. forn(i,m)
  73. {
  74. int x = a[i];
  75. int y = b[i];
  76. val[i]=0;
  77. forn(v,n)
  78. {
  79. if (can[x][v] && can[v][y])
  80. {
  81. ++val[i];
  82. continue;
  83. }
  84. if (can[y][v] && can[v][x])
  85. {
  86. ++val[i];
  87. continue;
  88. }
  89. if (can[y][v] && can[v][y])
  90. {
  91. ++val[i];
  92. continue;
  93. }
  94. if (can[x][v] && can[v][x])
  95. {
  96. ++val[i];
  97. continue;
  98. }
  99. }
  100. }
  101.  
  102. int res = *max_element(val, val+m);
  103. printf("%d\n",res);
  104. int cnt=0;
  105. forn(i,m)if(val[i]==res)++cnt;
  106. printf("%d\n", cnt);
  107. forn(i,m)if(val[i]==res)printf("%d ",i+1);
  108. printf("\n");
  109. return 0;
  110. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement