Cod sursa(job #1117134)

Utilizator toranagahVlad Badelita toranagah Data 23 februarie 2014 09:00:31
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.88 kb
#include <algorithm>
#include <fstream>
#include <iostream>
#include <stack>
#include <vector>
using namespace std;

ifstream fin("biconex.in");
ofstream fout("biconex.out");

typedef pair<int, int> Edge;

const int INF = 1 << 30;
const int MAX_N = 100100;

int N, M;
vector<int> graph[MAX_N];
vector<vector<int>> biconex;
stack<Edge> edge_stack;
int depth[MAX_N];
int lowest[MAX_N];
bool visited[MAX_N];

void read_input();
void dfs(int node);
void print_output();
void get_component(const Edge &start);

int main() {
    read_input();
    dfs(1);
    print_output();
    return 0;
}

void read_input() {
    fin >> N >> M;
    for (int i = 1, a, b; i <= M; i += 1) {
        fin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
}

void dfs(int node) {
    visited[node] = true;

    lowest[node] = depth[node];
    for (auto son: graph[node]) {
        if (visited[son]) {
            lowest[node] = min(lowest[node], depth[son]);
            continue;
        }

        depth[son] = depth[node] + 1;
        edge_stack.push(make_pair(node, son));
        dfs(son);

        if (lowest[son] >= depth[node]) {
            get_component(make_pair(node, son));
        }

        lowest[node] = min(lowest[node], lowest[son]);
    }
}

void get_component(const Edge &start) {
    biconex.push_back(vector<int>());
    vector<int> &c = biconex.back();

    while (edge_stack.top() != start) {
        c.push_back(edge_stack.top().first);
        c.push_back(edge_stack.top().second);
        edge_stack.pop();
    }

    c.push_back(edge_stack.top().first);
    c.push_back(edge_stack.top().second);
    edge_stack.pop();

    sort(c.begin(), c.end());
    c.resize(unique(c.begin(), c.end()) - c.begin());
}

void print_output() {
    fout << biconex.size() << '\n';
    for (auto c: biconex) {
        for (auto i: c) {
            fout << i << ' ';
        }
        fout << '\n';
    }
}