Cod sursa(job #1677796)

Utilizator papinubPapa Victor papinub Data 6 aprilie 2016 19:46:54
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.15 kb
# include <cstdio>
# include <vector>
# include <stack>
# include <algorithm>

using namespace std;

FILE *f = freopen("biconex.in", "r", stdin);
FILE *g = freopen("biconex.out", "w", stdout);

const int N_MAX = 100001;

vector <int> G[N_MAX];
stack <pair<int, int>> stiva;
vector <int> componente[N_MAX];
int nivel[N_MAX];
int dp[N_MAX];
int total, n, m;

void read()
{
    scanf("%d %d", &n, &m);

    for (int i=1; i<=m; i++)
    {
        int x, y;
        scanf("%d %d", &x, &y);

        G[x].push_back(y);
        G[y].push_back(x);
    }

    for (int i=1; i<=n; i++)
        nivel[i] = -2;
}

void add_comp_biconexa(int finish1, int finish2)
{
    pair <int, int> current = stiva.top();

    total ++;

    componente[total].push_back(current.first);
    componente[total].push_back(current.second);

    while (current.first != finish1 && current.second != finish2)
    {
        stiva.pop();
        current = stiva.top();

        componente[total].push_back(current.first);
        componente[total].push_back(current.second);
    }

    stiva.pop();
}

void dfs(int nod, int niv)
{
    dp[nod] = niv;
    nivel[nod] = niv;

    for (int i : G[nod])
    {
        if (nivel[i] + 1 == nivel[nod]) /// tata
            continue;

        if (!dp[i]) /// fiu din subarbore
        {
            stiva.push(make_pair(nod, i));
            dfs(i, niv + 1);

            dp[nod] = min(dp[nod], dp[i]);

            if (dp[i] >= nivel[nod]) /// nod este punct de articulatie / critic
                add_comp_biconexa(nod, i); /// adaugam pana la muchia nod - i inclusiv
        }
        else
            dp[nod] = min(dp[nod], dp[i]); /// muchie de intoarcere
    }
}

void write()
{
    printf("%d\n", total);

    for (int i=1; i<=total; i++)
    {
        sort(componente[i].begin(), componente[i].end());
        componente[i].resize(unique(componente[i].begin(), componente[i].end()) - componente[i].begin());

        for (int nod : componente[i])
            printf("%d ", nod);

        printf("\n");
    }
}

int main()
{
    read();
    dfs(1, 1);
    write();
    return 0;
}