Cod sursa(job #581839)

Utilizator mottyMatei-Dan Epure motty Data 14 aprilie 2011 17:28:32
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.15 kb
#include <fstream>
#include <vector>
#include <deque>
#include <algorithm>

using namespace std;

ifstream in("biconex.in");
ofstream out("biconex.out");

struct edge{
    int a, b;
};

const int N = 100001;

int n;
int biCount;
int fat[N];
int h[N];
int up[N];

bool vis[N];

vector <int> g[N];
vector <int> b[N];
deque <edge> e;

void Read()
{
    int n, m;
    in >> n >> m;

    while (m--)
    {
        int a, b;
        in >> a >> b;

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

void DiggIn(int node)
{
    vis[node] = true;
    up[node] = h[node];

    for (int i = 0; i < g[node].size(); ++i)
    {
        int next = g[node][i];

        if (!vis[next])
        {
            edge curEdge;

            curEdge.a = node;
            curEdge.b = next;

            e.push_back(curEdge);

            fat[next] = node;
            h[next] = h[node] + 1;

            DiggIn(next);

            if (up[next] < up[node])
                up[node] = up[next];

            if (up[next] >= h[node])
            {
                ++biCount;
                curEdge = e.back();

                while (curEdge.a != node || curEdge.b != next)
                {
                    b[biCount].push_back(curEdge.a);
                    b[biCount].push_back(curEdge.b);

                    e.pop_back();
                    curEdge = e.back();
                }

                b[biCount].push_back(curEdge.a);
                b[biCount].push_back(curEdge.b);

                e.pop_back();
            }
        }
        else if (fat[node] != next && h[next] < h[node])
        {
            if (up[node] > h[next])
                up[node] = h[next];

            edge curEdge;

            curEdge.a = node;
            curEdge.b = next;

            e.push_back(curEdge);
        }
    }
}

void Print()
{
    out << biCount << "\n";

    for (int i = 1; i <= biCount; ++i)
    {
        sort(b[i].begin(), b[i].end());
        b[i].resize( unique(b[i].begin(), b[i].end()) - b[i].begin());

        for (int j = 0; j < b[i].size(); ++j)
            out << b[i][j] << " ";

        out << "\n";
    }
}

int main()
{
    Read();
    DiggIn(1);
    Print();

    return 0;
}