Cod sursa(job #1821917)

Utilizator Vlad_317Vlad Panait Vlad_317 Data 3 decembrie 2016 21:34:16
Problema Componente biconexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.64 kb
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

const int MAX = 100000;

vector<int> g[MAX + 1], bc[MAX + 1];
int nrbc;
pair<int, int> st[MAX + 1];
int top;
int dfn[MAX + 1], low[MAX + 1];

void biconex(int x, int y)
{
    nrbc++;
    pair<int, int> p = {x, y}, q;
    q = st[top];
    top--;

    while(p != q)
    {
        bc[nrbc].push_back(q.first);
        bc[nrbc].push_back(q.second);

        q = st[top];
        top--;
    }
    bc[nrbc].push_back(q.first);
    bc[nrbc].push_back(q.second);
}

void dfs(int nod, int nr)
{
    dfn[nod] = low[nod] = nr;
    for(int i = 0; i < g[nod].size(); i++)
        if(dfn[g[nod][i]] == 0)
        {
            st[++top] = {nod, g[nod][i]};
            dfs(g[nod][i], nr + 1);
            low[nod] = min(low[nod], low[g[nod][i]]);

            if(low[g[nod][i]] >= dfn[nod])
                biconex(nod, g[nod][i]);
        }
        else
            low[nod] = min(low[nod], dfn[g[nod][i]]);
}

int main()
{
    FILE *fin, *fout;

    fin = fopen("biconex.in", "r");
    fout = fopen("biconex.out", "w");

    int n, m;

    fscanf(fin, "%d%d", &n, &m);

    for(int i = 1; i <= m; i++)
    {
        int x, y;
        fscanf(fin, "%d%d", &x, &y);
        g[x].push_back(y);
        g[y].push_back(x);
    }

    dfs(1, 1);

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

    return 0;
}