Cod sursa(job #1252282)

Utilizator SmarandaMaria Pandele Smaranda Data 30 octombrie 2014 16:47:52
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.41 kb
#include <cstdio>
#include <vector>
#include <stack>

using namespace std;

const int N = 100002;

struct Edge {
    int x, y;
    bool operator != (const Edge &other) {
        return (!(x == other.x && y == other.y));
    }
};

int n, m, biconexe, dp [N], level [N], f [N], a [N];
bool used [N];
vector <Edge> ans [N];
vector <int> graph [N];
stack <Edge> st;

void dfs (int x) {
    vector <int> :: iterator it;
    Edge temp;

    used [x] = 1;
    dp [x] = level [x];
    for (it = graph [x].begin (); it != graph [x].end (); ++ it)
        if (*it != f [x]) {
            temp.x = x;
            temp.y = *it;
            if (!used [*it]) {
                st.push (temp);
                level [*it] = level [x] + 1;
                f [*it] = x;
                dfs (*it);
                dp [x] = min (dp [x], dp [*it]);
                if (dp [*it] >= level [x]) {
                    ++ biconexe;
                    while (st.top () != temp) {
                        ans [biconexe].push_back (st.top ());
                        st.pop ();
                    }
                    ans [biconexe].push_back (st.top ());
                    st.pop ();

                }
            }
            else {
                if (level [*it] < level [x]) {
                    dp [x] = min (dp [x], level [*it]);
                    st.push (temp);
                }
            }
    }
}

int main () {
    int i, x, y;
    vector <Edge> :: iterator it;

    freopen ("biconex.in", "r", stdin);
    freopen ("biconex.out", "w", stdout);

    scanf ("%d%d", &n, &m);
    for (i = 1; i <= m; i ++) {
        scanf ("%d%d", &x, &y);
        graph [x].push_back (y);
        graph [y].push_back (x);
    }
    biconexe = 0;
    for (i = 1; i <= n; i ++)
        if (!used [i])
            dfs (i);
    printf ("%d\n", biconexe);
    for (i = 1; i <= biconexe; i ++) {
        for (it = ans [i].begin (); it != ans [i].end (); ++ it) {
            a [(*it).x] = i;
            a [(*it).y] = i;
        }
        for (it = ans [i].begin (); it != ans [i].end (); ++ it) {
            if (a [(*it).x] == i) {
                printf ("%d ", (*it).x);
                a [(*it).x] = 0;
            }
            if (a [(*it).y] == i) {
                printf ("%d ", (*it).y);
                a [(*it).y] = 0;
            }
        }
        printf ("\n");
    }
    return 0;
}