Cod sursa(job #791091)

Utilizator repp4raduRadu-Andrei Szasz repp4radu Data 22 septembrie 2012 21:28:05
Problema Componente biconexe Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.67 kb
#include <fstream>
#include <vector>
#include <stack>
#include <cstring>

#define MAX 131072

using namespace std;

vector<int> v[MAX], lvl, highest;
vector< vector < int > > sol;
stack< pair < int , int > > stk;
int n, m, a, b, ap[MAX];

void addSolution(int x, int y)
{
    vector<int> s; int X, Y;
    do
    {
        X = stk.top().first; Y = stk.top().second;
        s.push_back(X); s.push_back(Y);
        stk.pop();
    } while(X != x || Y != y);
    sol.push_back(s);
}

void df(int nod, int dad, int level)
{
    lvl[nod] = highest[nod] = level;
    for(int i = 0; i < v[nod].size(); i++)
    {
        if(v[nod][i] == dad) continue;
        if(lvl[v[nod][i]] == -1)
        {
            stk.push(make_pair(nod, v[nod][i]));
            df(v[nod][i], nod, level + 1);
            highest[nod] = min(highest[nod], highest[v[nod][i]]);
            if(lvl[nod] <= highest[v[nod][i]])
                addSolution(nod, v[nod][i]);
        }
        else
            highest[nod] = min(highest[nod], lvl[v[nod][i]]);
    }
}

int main()
{
    ifstream in("biconex.in");
    in>>n>>m;
    lvl.assign(n + 1, -1);
    highest.assign(n + 1, -1);
    for(int i = 1; i <= m; i++)
    {
        in>>a>>b;
        v[a].push_back(b); v[b].push_back(a);
    }
    in.close();
    df(1, 0, 0);
    ofstream out("biconex.out");
    out<<sol.size()<<"\n";
    for(int i = 0; i < sol.size(); i++)
    {
        memset(ap, 0, sizeof(ap));
        for(int j = 0; j < sol[i].size(); j++)
            ap[sol[i][j]] = 1;
        for(int j = 1; j <= n; j++)
            if(ap[j]) out<<j<<" ";
        out<<"\n";
    }
    out.close();
    return 0;
}