Cod sursa(job #1377068)

Utilizator MarronMarron Marron Data 5 martie 2015 19:56:57
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.95 kb
#include <cstring>
#include <iostream>
#include <fstream>
#include <vector>
#include <bitset>
#include <stack>
#include <set>


typedef std::vector<int>::iterator iter;
typedef std::set<int>::iterator siter;


const int MAXN = 100005;
const int MAXM = 200005;
std::ifstream f("biconex.in");
std::ofstream g("biconex.out");
std::vector<int> G[MAXN]; int n, m;
int t[MAXN];
int low[MAXN];
int level[MAXN];
std::bitset<MAXN> viz;
std::stack< std::pair<int, int> > st;
std::vector< std::set<int> > comps;


int dfs(int node, int lv = 1)
{
    viz[node] = true;
    level[node] = lv;
    low[node] = lv;

    for (iter it = G[node].begin(); it != G[node].end(); it++) {
        if (*it == t[node]) {
            continue;
        }

        if (viz[*it] == true) {
            low[node] = std::min(low[node], level[*it]);
        }
        else {
            t[*it] = node;
            st.push(std::make_pair(node, *it));
            low[node] = std::min(low[node], dfs(*it, lv + 1));
        }
    }


    if (low[node] >= level[t[node]]) {
        comps.push_back(std::set<int>());
        while (st.top() != std::make_pair(t[node], node)) {
            comps.back().insert(st.top().first);
            comps.back().insert(st.top().second);
            st.pop();
        }
        comps.back().insert(t[node]);
        comps.back().insert(node);
        st.pop();
    }

    return low[node];
}


int main()
{
    memset(level, 0x3f, sizeof(level));
    memset(low, 0x3f, sizeof(low));

    f >> n >> m;
    for (int i = 1, x, y; i <= m; i++) {
        f >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }


    dfs(1);


    g << comps.size() << '\n';
    for (int i = 0; i < comps.size(); i++) {
        for (siter it = comps[i].begin(); it != comps[i].end(); it++) {
            g << *it << ' ';
        }
        g << '\n';
    }


    f.close();
    g.close();
    return 0;
}