Cod sursa(job #1165584)

Utilizator tzipleatudTudor Tiplea tzipleatud Data 2 aprilie 2014 19:24:22
Problema Santa Scor 0
Compilator cpp Status done
Runda Lista lui wefgef Marime 2.17 kb
#include <fstream>
#include <stack>
#include <vector>
#include <cassert>
#include <algorithm>
#define NM 100010

using namespace std;

ifstream f("santa.in");
ofstream g("santa.out");

int N, M, K;
vector<int> G[NM];
vector<int> Component[NM];
int Level[NM], LowPoint[NM];
stack< pair<int, int> > S;

void DF (int node, int father)
{
    LowPoint[node]=Level[node];

    for (vector<int>::iterator it=G[node].begin(); it!=G[node].end(); ++it)
    {
        if (*it==father)
            continue;

        if (Level[*it]==0)
        {
            Level[*it]=Level[node]+1;
            S.push(make_pair(node, *it));
            DF(*it, node);

            LowPoint[node]=min(LowPoint[node], LowPoint[*it]);

            if (LowPoint[*it]>=Level[node]) // am punct de articulatie
            {
                K++;
                for (; !S.empty() && S.top()!=make_pair(node, *it); S.pop())
                {
                    Component[K].push_back(S.top().first);
                    Component[K].push_back(S.top().second);
                }
                if (!S.empty() && S.top()==make_pair(node, *it))
                {
                    Component[K].push_back(S.top().first);
                    Component[K].push_back(S.top().second);
                    S.pop();
                }
            }
        }
        else
            LowPoint[node]=min(LowPoint[node], Level[*it]);
    }
}

int main ()
{
    f >> N >> M;
    for (int i=1; i<=M; i++)
    {
        int x, y;
        f >> x >> y;

        G[x].push_back(y);
        G[y].push_back(x);
    }

    for (int i=1; i<=N; i++)
        if (!Level[i])
        {
            Level[i]=1;
            DF(i, 0);
        }

    g << K << '\n';
    for (int i=1; i<=K; i++)
    {
        sort(Component[i].begin(), Component[i].end());
        Component[i].erase(unique(Component[i].begin(), Component[i].end()), Component[i].end());
        assert(Component[i].size()<=15);

        for (vector<int>::iterator it=Component[i].begin(); it!=Component[i].end(); ++it)
            g << (*it) << ' ';

        g << '\n';
    }

    f.close();
    g.close();

    return 0;
}