Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <string>
- #include <stack>
- #include <set>
- #include <map>
- #include "optimization.h"
- #include <unordered_map>
- using namespace std;
- vector<vector<int>> tree;
- int n, e;
- map<pair<int, int>, int> mem;
- vector<int> time_;
- vector<int> min_time;
- stack<int> stack_;
- int T = 0;
- vector<vector<int>> result;
- multiset<pair<int,int>> mark;
- void relax(int &a, int &b) {
- if (b < a) {
- a = b;
- }
- }
- void dfs(int root, int parent) {
- stack_.push(root);
- time_[root] = min_time[root] = ++T;
- for (auto x: tree[root]) {
- if (x == parent) continue;
- if (!time_[x]) {
- int stack_lvl = stack_.size();
- dfs(x, root);
- relax(min_time[root], min_time[x]);
- if (min_time[x] > time_[root] && (mark.count({min(root,x), max(root,x)}) == 1)) {
- vector<int> tmp;
- while (stack_.size() > stack_lvl) {
- tmp.push_back(stack_.top());
- stack_.pop();
- }
- if (!tmp.empty()) result.push_back(tmp);
- // result.insert(y);
- }
- } else {
- relax(min_time[root], time_[x]);
- }
- }
- }
- int main() {
- // cin >> n >> e;
- n = readInt();
- e = readInt();
- // mark.resize(n+1, vector<int>(n+1, 0));
- tree.resize(n + 1);
- time_.resize(n + 1, 0);
- min_time.resize(n + 1);
- for (int i = 1; i <= e; i++) {
- int a, b;
- // cin >> a >> b;
- a = readInt();
- b = readInt();
- if (a > b) {
- swap(a, b);
- }
- mark.insert({a,b});
- tree[a].push_back(b);
- tree[b].push_back(a);
- }
- for (int v = 1; v <= n; v++) {
- int stack_lvl = stack_.size();
- if (time_[v] == 0) { dfs(v, 0); }
- vector<int> tmp;
- while (stack_.size() > stack_lvl) {
- tmp.push_back(stack_.top());
- stack_.pop();
- }
- if (!tmp.empty()) {
- result.push_back(tmp);
- }
- }
- for (auto &x : result){
- sort(x.begin(), x.end());
- }
- sort(result.begin(), result.end());
- // cout << result.size() << '\n';
- writeInt(result.size(), '\n');
- for (auto &x: result) {
- // cout << x << '\n';
- // sort(x.begin(), x.end());
- for (auto &y: x) {
- writeInt(y, ' ');
- // cout << y << " ";
- }
- writeChar('\n');
- //cout << '\n';
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement