Cod sursa(job #987506)

Utilizator cbanu96Banu Cristian cbanu96 Data 20 august 2013 21:30:28
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.83 kb
#include <cstdio>
#include <utility>
#include <stack>
#include <vector>
#include <algorithm>

#define FILEIN "biconex.in"
#define FILEOUT "biconex.out"

using namespace std;

const int NMAX = 100002;

int N, M;
int lvl[NMAX], low[NMAX], f[NMAX];
vector<int> A[NMAX];
vector< vector<int> > Sol;
stack< pair<int, int> > st;

void dfs( int node ) {
    low[node] = lvl[node];
    for ( size_t i = 0; i < A[node].size();  i++ )
    {
        if (f[A[node][i]])
            continue;
        f[A[node][i]] = node, lvl[A[node][i]] = lvl[node] + 1;
        st.push(make_pair(node, A[node][i]));
        dfs(A[node][i]);
        if (low[A[node][i]] >= lvl[node]) {
            vector<int> tmp;
            while (st.top().first != node && st.top().second != A[node][i])
                tmp.push_back(st.top().first), tmp.push_back(st.top().second), st.pop();
            tmp.push_back(node), tmp.push_back(A[node][i]), st.pop();
            Sol.push_back(tmp);
        }
    }

    for (size_t i = 0; i < A[node].size(); i++)
        if (A[node][i] != f[node])
            low[node] = min(low[node], low[A[node][i]]);
}

int main() {
    int x, y;
    freopen(FILEIN, "r", stdin);
    freopen(FILEOUT, "w", stdout);

    scanf("%d %d", &N, &M);
    for ( int i = 1; i <= M; i++) {
        scanf("%d %d", &x, &y);
        A[x].push_back(y);
        A[y].push_back(x);
    }

    for ( int i = 1; i <= N; i++)
        if (!f[i])
            f[i] = i, dfs(i);

    printf("%d\n", Sol.size());
    for ( size_t i = 0; i < Sol.size(); i++) {
        sort(Sol[i].begin(), Sol[i].end());
        printf("%d ", Sol[i][0]);
        for ( size_t j = 1; j < Sol[i].size(); j++ ) {
            if ( Sol[i][j] != Sol[i][j-1])
                printf("%d ", Sol[i][j]);
        }
        printf("\n");
    }

    return 0;
}