Cod sursa(job #2199528)

Utilizator larisamLarisa Togoe larisam Data 28 aprilie 2018 09:31:03
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.37 kb
#include <bits/stdc++.h>
using namespace std;

const int kNmax = 100005;

class Task {
public:
    void solve() {
        read_input();
        print_output(get_result());
    }

private:
    int n, m, time = 0;
    vector<int> adj[kNmax];
    vector<int> idx;
    vector<int> low;
    vector<int> parent;

    void read_input() {
        int i, a, b;
        ifstream f("biconex.in");
        //std::cin>>n>>m;
        f >> n >> m;
        for (i = 1; i <= m; i++) {
            f >> a >> b;
            //std::cin>>a>>b;
            adj[a].push_back(b);
            adj[b].push_back(a);
        }
        f.close();
    }

    void dfs(int i, stack<int> &stk, vector<vector<int>> &bccs) {
        int childrens = 0, j, z;
        time++;
        idx[i] = time;
        low[i] = time;
        stk.push(i);
        for (int u : adj[i]) {
            if (!idx[u]) {
                childrens++;
                parent[u] = i;
                dfs(u, stk, bccs);
                low[i] = min(low[i], low[u]);

                if (low[u] >= idx[i] && parent[i] || !parent[i]) {
                    vector<int> bcc;
                    bcc.push_back(i);
                    do {
                        z = stk.top();
                        stk.pop();
                        bcc.push_back(z);
                    } while (z != u);
                    bccs.push_back(bcc);
                }
            } else if (u != parent[i]) {
                low[i] = min(low[i], idx[u]);
            }
        }
    }

    vector<vector<int>> get_result() {
        int i;
        vector<vector<int>> sol;
        stack<int> stk;
        idx.resize(n + 1, 0);
        low.resize(n + 1);
        parent.resize(n + 1, 0);

        for (i = 1; i <= n; i++)
            if (!idx[i])
                dfs(i, stk, sol);

        return sol;
    }

    void print_output(vector<vector<int>> result) {
        int i, j;
        ofstream g("biconex.out");
        //std::cout<<std::endl;
        //std::cout<<result.size()<<std::endl;
        g << result.size() << '\n';
        for (i = 0; i < result.size(); i++) {
            for (j = 0; j < result[i].size(); j++)
                //std::cout<<result[i][j]<<" ";
                g << result[i][j] << ' ';
            //std::cout<<std::endl;
            g << '\n';
        }
        g.close();
    }
};

int main() {
    Task *task = new Task();
    task->solve();
    delete task;
    return 0;
}