Cod sursa(job #1378438)

Utilizator radarobertRada Robert Gabriel radarobert Data 6 martie 2015 12:11:49
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.73 kb
#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

const int MAXN = 100002;

vector<int> g[MAXN];
vector< vector<int> > sol;
stack< pair<int, int> > st;
int dfn[MAXN], low[MAXN];

int Min(int a, int b)
{
    if (a < b)
        return a;
    return b;
}

void addSol(int x, int y)
{
    vector<int> v;
    int a, b;
    do
    {
        a = st.top().first;
        b = st.top().second;
        v.push_back(a);
        v.push_back(b);
        st.pop();
    } while (a != x || b != y);
    sol.push_back(v);
}

void dfs(int x, int px, int level)
{
    dfn[x] = low[x] = level;
    for (int i = 0; i < g[x].size(); i++)
    {
        if (px == g[x][i])
            continue;
        if (dfn[g[x][i]] == 0)
        {
            st.push(make_pair(x, g[x][i]));
            dfs(g[x][i], x, level+1);
            low[x] = Min(low[x], low[g[x][i]]);
            if (low[g[x][i]] >= dfn[x])
                addSol(x, g[x][i]);
        }
        else
            low[x] = min(low[x], dfn[g[x][i]]);
    }
}

int main()
{
    FILE *in = fopen("biconex.in", "r");
    FILE *out = fopen("biconex.out", "w");

    int n, m;
    fscanf(in, "%d%d", &n, &m);
    for (int x, y; m > 0; m--)
    {
        fscanf(in, "%d%d", &x, &y);
        g[x].push_back(y);
        g[y].push_back(x);
    }

    dfs(1, 0, 1);

    fprintf(out, "%d\n", sol.size());
    for (int i = 0; i < sol.size(); i++)
    {
        sort(sol[i].begin(), sol[i].end());
        sol[i].erase(unique(sol[i].begin(), sol[i].end()), sol[i].end());
        for (int j = 0; j < sol[i].size(); j++)
            fprintf(out, "%d ", sol[i][j]);
        fprintf(out, "\n");
    }

    return 0;
}