Guest User

Untitled

a guest
Jan 29th, 2016
426
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.92 KB | None | 0 0
  1. #include <iostream>
  2. #include <iomanip>
  3. #include <cstdlib>
  4. #include <algorithm>
  5. #include <fstream>
  6. #include <cstdio>
  7. #include <cmath>
  8. #include <cstring>
  9. #include <string>
  10. #include <ctime>
  11. #include <queue>
  12. #include <stack>
  13. #include <vector>
  14. #include <map>
  15. #include <set>
  16. #include <deque>
  17.  
  18. using namespace std;
  19.  
  20. #define fi first
  21. #define se second
  22. #define mp make_pair
  23. #define sz(x) ((int)(x).size())
  24. #define pb(x) push_back(x)
  25. #define pf(x) push_front(x)
  26. #define abs(x) ((x) < 0 ? -(x) : (x))
  27. #define INF 2000000000
  28. #define sqr(x) ((x) * (x))
  29. #define all(x) x.begin(), x.end()
  30. #define fname ""
  31. #define MOD 1000000007
  32. #define y1 google
  33. #define tim printf("%.4lf\n", (clock() * 1.) / CLOCKS_PER_SEC)
  34.  
  35. int timer = 1, kol;
  36.  
  37. int tin[100500], fup[100500];
  38. vector <int> a[200500],w[200500];
  39. int ans[200500];
  40. bool was[100500];
  41.  
  42. void dfs(int v, int p) {
  43.      was[v] = true;
  44.      tin[v] = fup[v] = timer++;
  45.      for (int j = 0; j < a[v].size(); ++j) {
  46.          int to = a[v][j];
  47.          if (to == p) continue;
  48.          if (was[to]) {
  49.             fup[v] = min(fup[v], tin[to]);      
  50.          } else {
  51.             dfs(to, v);
  52.             fup[v] = min(fup[to], fup[v]);
  53.             if (fup[to] > tin[v]) {
  54.                ans[++kol] = w[v][j];
  55.             }
  56.          }
  57.      }                                  
  58. }
  59.  
  60. int main() {
  61.     freopen(fname".in", "r", stdin);
  62.     freopen(fname".out", "w", stdout);
  63.     int n, m;
  64.     scanf("%d%d", &n, &m);
  65.     for (int i = 1; i <= m; ++i) {
  66.         int x,y;
  67.         scanf("%d%d", &x, &y);
  68.         a[x].push_back(y);
  69.         a[y].push_back(x);
  70.         w[x].push_back(i);
  71.         w[y].push_back(i);
  72.     }
  73.     for (int i = 1; i <= n; ++i) {
  74.         if (!was[i]) {
  75.            dfs(i, -1);
  76.         }
  77.     }
  78.     sort(ans + 1, ans + 1 + kol);
  79.     printf("%d\n", kol);
  80.     for (int i = 1; i <= kol; ++i) {
  81.         printf("%d ", ans[i]);
  82.     }              
  83.     return 0;
  84. }
Add Comment
Please, Sign In to add comment