Cod sursa(job #779613)

Utilizator wefgefAndrei Grigorean wefgef Data 18 august 2012 11:39:23
Problema Componente biconexe Scor 46
Compilator cpp Status done
Runda Arhiva educationala Marime 1.9 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);
   }
}

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<int> comp;
                while (!edge_stack.empty() && edge_stack.top() != make_pair(father[node], node)) {
                    pair<int, int> edge = edge_stack.top();
                    edge_stack.pop();
                    comp.push_back(edge.first);
                    comp.push_back(edge.second);
                }

                sort(comp.begin(), comp.end());
                comp.resize(unique(comp.begin(), comp.end()) - comp.begin());
                sol.push_back(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();
}