Cod sursa(job #781384)

Utilizator tzipleatudTudor Tiplea tzipleatud Data 24 august 2012 13:00:18
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.98 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>
#define NM 100010


using namespace std;

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

typedef pair<int, int> PI;

bool Equal (const PI& a, const PI& b)
{
    return ((a.first==b.first && a.second==b.second) || (a.first==b.second && a.second==b.first));
}

vector<int> G[NM];
vector<int> ANS[NM];
stack<PI> S;
PI A,B;

int N,M,K,i,a,b;
int LVL[NM],D[NM];

void DF (int nod, int t)
{
    D[nod]=LVL[nod];
    for (unsigned int i=0; i<G[nod].size(); i++)
    {
        if (G[nod][i]==t) continue;
        if (!LVL[G[nod][i]])
        {
            LVL[G[nod][i]]=LVL[nod]+1;
            S.push(make_pair(G[nod][i],nod));
            DF(G[nod][i],nod);
            D[nod]=min(D[nod],D[G[nod][i]]);
            if (D[G[nod][i]]>=LVL[nod])
            {
                ++K;
                B=make_pair(G[nod][i],nod);
                if (!S.empty())
                {
                    do
                    {
                        A=S.top();
                        S.pop();
                        ANS[K].push_back(A.first);
                        ANS[K].push_back(A.second);
                    }
                    while (!S.empty() && !Equal(A,B));
                }
            }
            continue;
        }
        D[nod]=min(D[nod],D[G[nod][i]]);
    }
}

int main ()
{
    f >> N >> M;
    for (i=1; i<=M; i++)
    {
        f >> a >> b;
        G[a].push_back(b);
        G[b].push_back(a);
    }

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

    g << K << '\n';
    for (i=1; i<=K; i++)
    {
        sort(ANS[i].begin(),ANS[i].end());
        g << ANS[i][0] << ' ';
        for (unsigned int j=1; j<ANS[i].size(); j++)
            if (ANS[i][j]!=ANS[i][j-1])
                g << ANS[i][j] << ' ';
        g << '\n';
    }

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