Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- void Graph::brigdeUtil(int u, std::deque<bool>& visited, vector<int>& disc, vector<int>& low, vector<int>& parent) {
- static int time = 0;
- int children = 0;
- visited[u] = true;
- disc[u] = low[u] = ++time;
- for (auto i = graph[u].begin(); i != graph[u].end(); ++i) {
- int v = *i;
- if (!visited[v]) {
- children++;
- parent[v] = u;
- brigdeUtil(v, visited, disc, low, parent);
- low[u] = std::min(low[u], low[v]);
- if (low[v] > disc[u]) {
- auto it = counter.find(std::make_pair(u, v));
- auto it2 = counter.find(std::make_pair(v, u));
- if (it != counter.end()) {
- set_of_roads.insert(this->counter.at(std::make_pair(u, v)));
- }
- else if (it2 != counter.end()) {
- set_of_roads.insert(this->counter.at(std::make_pair(v, u)));
- }
- }
- if (parent[u] == NIL && children > 1)
- set_of_points.insert(u);
- if (parent[u] != NIL && low[v] >= disc[u])
- set_of_points.insert(u);
- }
- else if (v != parent[u]) {
- low[u] = std::min(low[u], disc[v]);
- }
- }
- }
- void Graph::get() {
- std::cout << set_of_roads.size() << std::endl;
- for (const auto& x : set_of_roads) {
- std::cout << x << std::endl;
- }
- std::cout << set_of_points.size() << std::endl;
- for (const auto& x : set_of_points) {
- std::cout << x << std::endl;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement