Cod sursa(job #779615)

Utilizator wefgefAndrei Grigorean wefgef Data 18 august 2012 11:57:27
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.04 kb
#include <algorithm>
#include <fstream>
#include <stack>
#include <vector>

using namespace std;

#define FORIT(it, v) for (typeof((v).begin()) it = (v).begin(); it != (v).end(); ++it)

const int MAX_N = 100005;

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

int n, m;
vector<int> graph[MAX_N];

bool vis[MAX_N];
int father[MAX_N];
int level[MAX_N];
int up[MAX_N];
stack< pair<int, int> > edge_stack;
vector< vector<int> > sol;

void read() {
   fin >> n >> m;
   for (int i = 0; i < m; ++i) {
       int a, b;
       fin >> a >> b;
       
       graph[a].push_back(b);
       graph[b].push_back(a);
   }
}

vector<int> unique_vals(vector< pair<int, int> > v) {
    vector<int> vals;
    FORIT(it, v) {
        vals.push_back(it->first);
        vals.push_back(it->second);
    }
    sort(vals.begin(), vals.end());
    vals.resize(unique(vals.begin(), vals.end()) - vals.begin());
    return vals;
}

void dfs(int node) {
    vis[node] = true;
    up[node] = level[node];

    FORIT(it, graph[node])
        if (!vis[*it]) {
            father[*it] = node;
            level[*it] = level[node] + 1;
            edge_stack.push(make_pair(node, *it));
            dfs(*it);

            // check dp
            up[node] = min(up[node], up[*it]);

            // new biconnected component found
            if (up[*it] >= level[node]) {
                vector< pair<int, int> > comp;
                while (edge_stack.top() != make_pair(node, *it)) {
                    comp.push_back(edge_stack.top());
                    edge_stack.pop();
                }
                comp.push_back(edge_stack.top());
                edge_stack.pop();

                sol.push_back(unique_vals(comp));
            }
        } else {
            // check dp
            if (level[*it] < level[node] - 1)
                up[node] = min(up[node], level[*it]);
        }
}

void write() {
    fout << sol.size() << "\n";
    FORIT(it, sol) {
        FORIT(it2, *it)
            fout << *it2 << " ";
        fout << "\n";
    }
}

int main() {
    read();
    dfs(1);
    write();
}