Cod sursa(job #2110324)

Utilizator ioanailincaMoldovan Ioana Ilinca ioanailinca Data 20 ianuarie 2018 15:47:20
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 3.68 kb
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cctype>
#include <stack>

using namespace std;
using vi = vector<int>;
using vb = vector<bool>;
using vvi = vector<vi>;

const int BUFF_SIZE = 1 << 17;

char buffer[BUFF_SIZE];
int buffPos = BUFF_SIZE;

FILE *f, *g;
int T = 1, n, root = 1, rootEdges;
vvi v;
vi t, levMin, lev;
vb seen;
stack<pair<int, int> > stk;
vvi biconexe;

inline char getChar() {
    if (buffPos == BUFF_SIZE) {
        fread(buffer, 1, BUFF_SIZE, f);
        buffPos = 0;
    }
    return buffer[buffPos++];
}

inline int getInt() {
    int ret = 0;
    char c;
    do {
        c = getChar();
    } while (!isdigit(c));

    do {
        ret = ret * 10 + c - '0';
        c = getChar();
    } while (isdigit(c));
    return ret;
}

inline void read() {
    f = fopen("biconex.in", "r");
    g = fopen("biconex.out", "w");
    int m;
   // T = getInt();
    n = getInt();
    m = getInt();
    seen = vb(n + 1);
    v = vvi(n + 1);
    t = levMin = lev = vi(n + 1);
    int x, y;
    for (int i = 1; i <= m; ++i) {
        x = getInt();
        y = getInt();
        v[x].push_back(y);
        v[y].push_back(x);
    }
}

inline void getComps(int x, int y) {
    vi cc;
    int xx, yy;
    do {
        xx = stk.top().first, yy = stk.top().second;
        stk.pop();
        cc.push_back(xx);
        cc.push_back(yy);
    } while (xx != x && yy != y);
    sort(cc.begin(), cc.end());
    cc.erase(unique(cc.begin(), cc.end()), cc.end());
    biconexe.push_back(cc);
}

void dfs(int node, int father) {
    seen[node] = 1;
    levMin[node] = lev[node] = lev[father] + 1;
    t[node] = father;
    if (lev[node] == 2)
        ++rootEdges;

    for (const int& other: v[node]) {
        if (other == father)
            continue;
        if (!seen[other]) {
            stk.push({node, other});
            dfs(other, node);
            levMin[node] = min(levMin[other], levMin[node]);

            if (levMin[other] >= lev[node])
                getComps(node, other);
        }
        else
            levMin[node] = min(levMin[node], lev[other]);
    }
}

inline void write() {
    if (T == 1) {
        for (auto c: biconexe) {
            fprintf(g, "%d ", (int)c.size());
            for (int i: c)
                fprintf(g, "%d ", i);
            fprintf(g, "\n");
        }
    }
    else if (T == 2) {
        int artPoints = 0;
        for (int i = 2; i <= n; ++i) {
            if (t[i] == root)
                continue;
            if (levMin[i] >= lev[t[i]])
                ++artPoints;
        }
        if (rootEdges > 1) {
            ++artPoints;
            fprintf(g, "%d\n%d", artPoints, root);
        }
        for (int i = 2; i <= n; ++i) {
            if (t[i] == root)
                continue;
            if (levMin[i] >= lev[t[i]])
                fprintf(g, "%d ", i);
        }
    }
    else {
        int m = 0;
        for (int i = 1; i <= n; ++i) {
            if (i == root)
                continue;
            if (levMin[i] > lev[t[i]])
                ++m;
        }
        fprintf(g, "%d\n", m);
        for (int i = 1; i <= n; ++i) {
            if (i == root)
                continue;
            if (levMin[i] > lev[t[i]])
                fprintf(g, "%d %d\n", t[i], i);
        }
    }
}

inline void writeInfoarena() {
    fprintf(g, "%d\n", biconexe.size());
    for (auto c: biconexe) {
        for (int i: c)
            fprintf(g, "%d ", i);
        fprintf(g, "\n");
    }
}

int main()
{
    read();
    dfs(root, 0);
    //write();
    writeInfoarena();

    fclose(f);
    fclose(g);
    return 0;
}