Cod sursa(job #1414448)

Utilizator valentin.harsanValentin Harsan valentin.harsan Data 2 aprilie 2015 17:04:03
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.25 kb
#include<iostream>
#include<fstream>
#include<cstdio>
#include<vector>
#include<string>
#include<cstring>
#include<queue>
#include<map>
#include<set>
#include<algorithm>
#include<iomanip>
#include<bitset>
using namespace std;

const int N = 110000;

int n, m, ver[N], f[N], niv[N], nivmin[N], lanti[N];
vector<int> v[N];
int st[N], top;
vector<vector<int> > rez;

void df(int nod)  {
    f[nod] = 1;

    for(vector<int>::iterator it = v[nod].begin(); it != v[nod].end(); ++it) if(!f[*it]) {
        niv[*it] = niv[nod] + 1;
        df(*it);
    }
}

void cb(int nod) {
    f[nod] = 1;
    nivmin[nod] = niv[nod];
    st[++top] = nod;

    for(vector<int>::iterator it = v[nod].begin(); it != v[nod].end(); ++it) {
        if(f[*it]) {
            nivmin[nod] = min(nivmin[nod], niv[*it]);

            if((niv[*it] - niv[nod]) % 2 == 0)
                lanti[nod] = 1;
        }
        else {

            cb(*it);

            nivmin[nod] = min(nivmin[nod], nivmin[*it]);

            if(nivmin[*it] >= niv[nod]) {
                int imp = 0;
                vector<int> el;

                while(1) {
                    if(lanti[st[top]])
                        imp = 1;

                    el.push_back(st[top]);
                    --top;

                    if(st[top + 1] == *it)
                        break;
                }

                el.push_back(nod);
                if(imp)
                    for(int i = 0; i < el.size(); ++i)
                        ver[el[i]] = 1;

                rez.push_back(el);
            }
        }
    }
}

int main() {
    int i;
    freopen("biconex.in", "r", stdin);
    freopen("biconex.out", "w", stdout);

    cin >> n >> m;

    for(i = 1; i <= m; ++i) {
        int a, b;
        cin >> a >> b;

        v[a].push_back(b);
        v[b].push_back(a);
    }

    for(i = 1; i <= n; ++i) if(!f[i])
        df(1);

    memset(f, 0, sizeof(f));
    for(i = 1; i <= n; ++i) if(!f[i])
        cb(i);


    cout << rez.size() << "\n";
    for(vector<vector<int> >::iterator it = rez.begin(); it != rez.end(); ++it) {
        for(i = 0; i < it->size(); ++i)
            cout << (*it)[i] << " ";
        cout << "\n";
    }

    return 0;
}