Участник:ZhenyaStrelkova/EC P

Материал из DISCOPAL
Перейти к: навигация, поиск

https://www.spoj.com/problems/EC_P/

#include <iostream>
#include <algorithm>
#include <vector>
 
using namespace std;
 
const int maximum = 707;
 
vector<vector<int>> graph;
vector<pair<int, int>> edges;
int NC, N, M, step;
int visited[maximum];
int stepIN[maximum];
int firstUp[maximum];
 
void dfs(int node, int parent = -1) {
    visited[node] = 1;
    stepIN[node] = ++step;
    firstUp[node] = step;
    for (int i : graph[node]) {
        if (i == parent) {
            continue;
        }
        if (visited[i]) {
            firstUp[node] = min(firstUp[node], stepIN[i]);
        } else {
            dfs(i, node);
            firstUp[node] = min(firstUp[node], firstUp[i]);
            if (firstUp[i] > stepIN[node]) {
                edges.emplace_back(make_pair(min(node, i), max(node, i)));
            }
        }
    }
}
 
int main() {
    cin >> NC;
    for (int t = 0; t < NC; t++) {
        cin >> N >> M;
        graph.resize(N + 1);
        for_each(graph.begin(), graph.end(), [](vector<int> &vec) { vec.clear(); });
        step = 0;
        edges.clear();
        for (int i = 1; i <= N; i++) {
            visited[i] = 0;
        }
 
        for (int i = 0; i < M; i++) {
            int a, b;
            cin >> a >> b;
            graph[a].push_back(b);
            graph[b].push_back(a);
        }
        for (int i = 0; i <= N; i++) {
            if (!visited[i]) dfs(i);
        }
        sort(edges.begin(), edges.end());
        edges.erase(unique(edges.begin(), edges.end()), edges.end());
 
        cout << "Caso #" << t + 1 << "\n";
        if (edges.empty()) {
            cout << "Sin bloqueos\n";
        } else {
            cout << (int) edges.size() << "\n";
            for (auto i : edges) {
                cout << i.first << " " << i.second << "\n";
            }
        }
    }
    return 0;
}