Cod sursa(job #1376914)

Utilizator MarronMarron Marron Data 5 martie 2015 19:23:36
Problema Componente biconexe Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 2.1 kb
#include <cstring>
#include <iostream>
#include <fstream>
#include <vector>
#include <bitset>
using namespace std;


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


const int INF = 0x3f3f3f3f;
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 parent[MAXN], low[MAXN], level[MAXN];
std::bitset<MAXN> viz;
std::pair<int, int> st[MAXN];
std::vector< std::vector<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 == parent[node]) {
            continue;
        }
        if (viz[*it] == true) {
            low[node] = min(low[node], level[*it]);
        }
        else {
            parent[*it] = node;
            st[++st[0].first] = make_pair(node, *it);
            low[node] = min(low[node], dfs(*it, lv + 1));
        }
    }

    if (low[node] >= level[parent[node]]) {
        //cout << node << endl;
        comps.push_back(vector<int>());
        while (st[st[0].first] != make_pair(parent[node], node)) {
            comps.back().push_back(st[st[0].first--].second);
        }
        comps.back().push_back(parent[node]);
        comps.back().push_back(node);
    }

    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);
    }


    parent[1] = 0;
    st[++st[0].first].first = 0;
    dfs(1);


    /*if (!st[0]) {
        comps.push_back(std::vector<int>());
        while (!st[0]) {
            comps.back().push_back(st[st[0]--]);
        }
    }*/


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


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