Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <algorithm>
- #include <map>
- #include <set>
- #define forn(i, n) for(int i = 1; i <= n; ++i)
- #define MAX 20001
- using namespace std;
- vector<vector<int>>graph(MAX);
- set <int> b;
- map<pair<int, int>, int> table; //чтобы в отсортированном виде
- int time[MAX], min_time[MAX];
- int n, m, T;
- #include <cassert>
- /** Begin fast allocation */
- const int MAX_MEM = 1e8;
- int mpos = 0;
- char mem[MAX_MEM];
- inline void * operator new ( size_t n ) {
- assert((mpos += n) <= MAX_MEM);
- return (void *)(mem + mpos - n);
- }
- inline void operator delete ( void * ) noexcept { } // must have!
- /** End fast allocation */
- void dfs (int v, int p) {
- time[v] = min_time[v] = ++T;
- for (int x : graph[v])
- if (x != p) {
- if (time[x] == 0) { // древесное ребро
- dfs(x, v);
- if (min_time[x] > time[v]) { // мост!
- b.insert(table[{v, x}]);
- }
- min_time[v] = min(min_time[v], min_time[x]);
- } else { // обратное или двойственное ему ребро в другую сторону
- min_time [v] = min(min_time[v], time [x]);
- }
- }
- }
- int main() {
- ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
- cin >> n >> m;
- int u, v;
- forn(i, m) {
- cin >> v >> u;
- graph[v].push_back(u);
- graph[u].push_back(v);
- table[{v, u}] = i;
- }
- T = 0;
- forn(i, n) if (!time[i]) dfs(i, 0);
- cout << b.size() << "\n";
- for (auto i = b.begin(); i != b.end(); i++) {
- cout << *i << "\n";
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement