Cod sursa(job #1099995)

Utilizator gabrielvGabriel Vanca gabrielv Data 6 februarie 2014 14:55:06
Problema Componente biconexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.16 kb
#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

#define NMAX 100010
#define minim(a,b) ((a<b)?(a):(b))

int N, M;
int AnhazlKomponenten;  // the number of biconex componenets

int Verbindung[NMAX];   // how much can I go up on the graph
int Tiefe[NMAX];        // depth

stack < pair < int , int > > Stapel;

vector < int > G[NMAX];
vector < int > Biconex[NMAX];

void Scannen()
{
    freopen("biconex.in","r",stdin);

    scanf("%d%d",&N,&M);

    for(int i=1,x,y;i<=M;i++)
    {
        scanf("%d%d",&x,&y);

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

void Berechnen(int Knoten1, int Knoten2)
{
    int x,y;
    AnhazlKomponenten++;

    do{
        x = Stapel.top().first;
        y = Stapel.top().second;
        Stapel.pop();
        Biconex[AnhazlKomponenten].push_back(x);
        Biconex[AnhazlKomponenten].push_back(y);

    }while(x != Knoten1 || y != Knoten2);
}

void DFS(int Knoten, int Vater)
{
    Verbindung [Knoten] = Tiefe[Knoten] = Tiefe[Vater] + 1;

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

        if(!Tiefe[*it])
        {
            Stapel.push(make_pair(Knoten, *it));

            DFS(*it, Knoten);

            Verbindung[Knoten] = minim(Verbindung[Knoten], Verbindung[*it]);

            if(Verbindung[*it] >= Tiefe[Knoten])
                Berechnen(Knoten, *it);

        }
        else
            Verbindung[Knoten] = minim(Verbindung[Knoten], Tiefe[*it]);

    }
}

void Drucken()
{
    //freopen("biconex.out", "w", stdout);

    printf("%d\n",AnhazlKomponenten);

    for(int i=1; i <= AnhazlKomponenten; i++)
    {
        sort(Biconex[i].begin(), Biconex[i].end());

        int Alt = -1;

        for(vector < int > :: iterator it = Biconex[i].begin(); it != Biconex[i].end(); ++ it)
        {
            if(Alt != *it)
                printf("%d ",*it);

            Alt = *it;
        }
        printf("\n");
    }
}

int main()
{
    Scannen();
    DFS(1,0);
    Drucken();
    return 0;
}