Cod sursa(job #1675956)

Utilizator andrei.arnautuAndi Arnautu andrei.arnautu Data 5 aprilie 2016 17:34:19
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.79 kb
/**
  *  Worg
  */
#include <stack>
#include <cstdio>
#include <vector>
#include <utility>
#include <algorithm>

using namespace std;
FILE *fin = freopen("biconex.in", "r", stdin);
FILE *fout = freopen("biconex.out", "w", stdout);

const int bufferDim = 100000;
const int MAX_N = 1 + 100000;

class inputReader {
private:
        char buffer[bufferDim];
        int pos = 0;

        bool digit(char c) {
            return('0' <= c && c <= '9');
        }

public:
        void getBuffer() {
            fread(buffer, 1, bufferDim, stdin);
            pos = 0;
        }

        void getInt(int &nr) {
            nr = 0;
            while(!digit(buffer[pos]))
                if(++pos == bufferDim)
                    getBuffer();
            while(digit(buffer[pos])) {

                nr = nr * 10 + buffer[pos] - '0';
                if(++pos == bufferDim)
                    getBuffer();
            }
        }
} cin;
/*---------------------*/
int N, M;
vector<int> G[MAX_N];
/*---------------------*/
stack< pair<int,int> > S;
vector< vector<int> > comp;
vector<int> now;
int level[MAX_N], dp[MAX_N];
/*---------------------*/


void readData() {
    cin.getBuffer();
    cin.getInt(N); cin.getInt(M);
    for(int i = 1; i <= M; ++i) {
        int u, v; cin.getInt(u); cin.getInt(v);
        G[u].push_back(v); G[v].push_back(u);
    }
}

void newComponent(pair<int,int> stop) {
    pair<int,int> top;
    now.clear();

    do {
        top = S.top();
        now.push_back(top.first); now.push_back(top.second);
        S.pop();
    }while(top != stop && !S.empty());

    /* vrem sa eliminam dublurile */
    sort(now.begin(), now.end());
    now.erase(unique(now.begin(), now.end()), now.end());
    comp.push_back(now);
}

void DFS(int node = 1, int father = 0) {
    dp[node] = level[node];
    for(vector<int>::iterator it = G[node].begin(); it != G[node].end(); ++it) {
        if(!level[*it]) { /* daca nu am parcurs deja nodul */
            level[*it] = level[node] + 1;
            S.push(make_pair(node, *it));
            DFS(*it, node);
            if(dp[*it] >= level[node]) { /* daca nodul este critic */
                newComponent(make_pair(node, *it));
            }
        }
    }

    for(vector<int>::iterator it = G[node].begin(); it != G[node].end(); ++it) {
        if(*it != father) {
            dp[node] = min(dp[node], dp[*it]);
        }
    }
}

void writeData() {
    printf("%d\n", (int)comp.size());
    for(int i = 0; i < (int)comp.size(); ++i) {
        for(vector<int>::iterator it = comp[i].begin(); it != comp[i].end(); ++it) {
            printf("%d ", *it);
        }
        printf("\n");
    }
}

int main() {
    readData();
    level[1] = 1;
    DFS();
    writeData();
    return 0;
}