Cod sursa(job #628675)

Utilizator nandoLicker Nandor nando Data 1 noiembrie 2011 20:59:44
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.93 kb
#include <iostream>
#include <algorithm>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;

#define MAXN 100100

int idx[MAXN], llink[MAXN];

vector<int> g[MAXN];
vector<vector<int> > comp;
stack<pair<int, int> > stk;

typedef vector<int>::iterator iter;
typedef vector<vector<int> >::iterator viter;
int n, m;

void dfs(int node, int from, int num)
{
    idx[node] = llink[node] = num;

    for (iter it = g[node].begin(); it != g[node].end(); ++it) {
        if (*it != from) {
            if (idx[*it] == -1) {
                stk.push(make_pair(node, *it));
                dfs(*it, node, num + 1);
                llink[node] = min(llink[node], llink[*it]);

                if (llink[*it] >= idx[node]) {
                    vector<int> c;
                    int x, y;

                    do {
                        x = stk.top().first;
                        y = stk.top().second;
                        stk.pop();

                        c.push_back(x);
                        c.push_back(y);
                    } while (x != node || y != *it);
                    sort(c.begin(), c.end());
                    c.erase(unique(c.begin(), c.end()), c.end());
                    comp.push_back(c);
                }
            } else {
                llink[node] = min(llink[node], idx[*it]);
            }
        }
    }
}

int main()
{
    fstream fin("biconex.in", ios::in);
    fstream fout("biconex.out", ios::out);

    fin >> n >> m;

    for (int i = 1; i <= n; ++i) {
        idx[i] = -1;
    }

    for (int i = 0, x, y; i < m; ++i) {
        fin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }

    dfs(1, 0, 0);

    fout << comp.size() << endl;

    for (viter it = comp.begin(); it != comp.end(); ++it) {
        for (iter jt = it->begin(); jt != it->end(); ++jt) {
            fout << *jt << " ";
        }
        fout << endl;
    }

    fin.close();
    fout.close();
    return 0;
}