Cod sursa(job #1620745)

Utilizator iordache.bogdanIordache Ioan-Bogdan iordache.bogdan Data 29 februarie 2016 12:27:38
Problema Componente biconexe Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 4.4 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <stack>

using namespace std;

ifstream fin("biconex.in");
ofstream fout("biconex.out");

const int dim = 2005;

int n;
int g[dim][dim];

vector<int> crit;

vector< pair<int, int> > critE, edges;

bool vis[dim];
void dfs(int node) {

    vis[node] = true;
    for (int i = 1; i <= n; ++i) {

        if (g[node][i] != 1 || vis[i])
            continue;

        dfs(i);

    }

}

bool isCrit(int node) {

    for (int i = 1; i <= n; ++i)
        if (g[node][i] == 1)
            g[node][i] = g[i][node] = -1;

    memset(vis, 0, sizeof vis);
    vis[node] = true;

    if (node != 1)
        dfs(1);
    else
        dfs(2);

    for (int i = 1; i <= n; ++i)
        if (g[node][i] == -1)
            g[node][i] = g[i][node] = 1;

    for (int i = 1; i <= n; ++i)
        if (!vis[i])
            return true;

    return false;

}

bool isCritE(int x, int y) {

    g[x][y] = g[y][x] = 0;

    memset(vis, 0, sizeof vis);

    dfs(x);

    g[x][y] = g[y][x] = 1;

    for (int i = 1; i <= n; ++i)
        if (!vis[i])
            return true;

    return false;

}

void dfs2(int node, vector<int> v, vector<int> &w) {

    vis[node] = true;

    w.push_back(node);

    for (unsigned int i = 0; i < v.size(); ++i) {

        if (!g[node][v[i]] || vis[v[i]])
            continue;

        dfs2(v[i], v, w);

    }

}

void dfs3(int node, vector<int> v) {

    vis[node] = true;

    for (unsigned int i = 0; i < v.size(); ++i) {

        if (g[node][v[i]] != 1 || vis[v[i]])
            continue;

        dfs3(v[i], v);

    }

}

bool isCrit2(int node, vector<int> v) {

    if (v.size() == 1)
        return false;

    for (int i = 1; i <= n; ++i)
        if (g[node][i] == 1)
            g[node][i] = g[i][node] = -1;

    memset(vis, 0, sizeof vis);
    vis[node] = true;

    if (node != v.back())
        dfs3(v.back(), v);
    else
        dfs3(v.front(), v);

    for (int i = 1; i <= n; ++i)
        if (g[node][i] == -1)
            g[node][i] = g[i][node] = 1;

    for (unsigned int i = 0; i < v.size(); ++i)
        if (!vis[v[i]])
            return true;

    return false;

}

int bc;
vector<int> BC[dim];

void solve(vector<int> v) {

    int root = 0;
    for (unsigned int i = 0; i < v.size(); ++i)
        if (isCrit2(v[i], v)) {root = v[i]; break;}

    if (root == 0) {

        ++bc;
        for (unsigned int i = 0; i < v.size(); ++i)
            BC[bc].push_back(v[i]);

    }
    else {

        memset(vis, 0, sizeof vis);
        vis[root] = true;

        vector<int> w;
        vector< vector<int> > aux;
        for (unsigned int i = 0; i < v.size(); ++i) {

            if (!g[root][v[i]] || vis[v[i]])
                continue;

            w.clear();
            w.push_back(root);
            dfs2(v[i], v, w);

            aux.push_back(w);

        }

        for (unsigned int i = 0; i < aux.size(); ++i)
            solve(aux[i]);

    }

}

int main() {

    int p = 1;
   // fin >> p;

    int m;
    fin >> n >> m;

    for (int i = 1; i <= m; ++i) {

        int x, y;
        fin >> x >> y;

        edges.push_back(make_pair(x, y));

        g[x][y] = g[y][x] = 1;

    }

    vector<int> v;

    if(p == 1) {

        for (int i = 1; i <= n; ++i)
            v.push_back(i);

        solve(v);

        fout << bc << '\n';
        for (int i = 1; i <= bc; ++i) {
            //fout << BC[i].size() << ' ';
            for (unsigned int j = 0; j < BC[i].size(); ++j)
                fout << BC[i][j] << ' ';
            fout << '\n';
        }

    }
    else if (p == 2) {

        for (int i = 1; i <= n; ++i)
            if (isCrit(i))
                crit.push_back(i);

        fout << crit.size() << '\n';
        for (unsigned int i = 0; i < crit.size(); ++i)
            fout << crit[i] << ' ';
        fout << '\n';

    }
    else {

        for (int i = 0; i < m; ++i) {

            if (isCritE(edges[i].first, edges[i].second))
                critE.push_back(edges[i]);

        }

        fout << critE.size() << '\n';
        for (unsigned int i = 0; i < critE.size(); ++i)
            fout << critE[i].first << ' ' << critE[i].second << '\n';


    }

    return 0;

}

//Trust me, I'm the Doctor!