Cod sursa(job #395551)

Utilizator cristiprgPrigoana Cristian cristiprg Data 13 februarie 2010 13:57:31
Problema Componente biconexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.79 kb
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
#define DIM 100005
#define pb push_back
struct nod
{
    int x;
    nod *next;
};

struct Stack
{
    int u, v;
} stack[DIM];


nod *G[DIM];
int top,n, m, v[DIM], lowpoint[DIM], depth[DIM], adancime, Count;
vector <Stack> comp[DIM];

void addMuchie(int i, int j)
{
    nod *p = new nod;
    p->x = j;
    p->next = G[i];
    G[i] = p;
}

void afis()
{
    for (int i = 1; i <= n; ++i)
    {
        printf ("%d:", i);
        for (nod *p = G[i]; p; p = p->next)
            printf ("%d ", p->x);
        printf ("\n");
    }
}

void update(int x, int y)
{
    ++Count;
    Stack s;
    do
    {
        s.u = stack[top].u;
        s.v = stack[top].v;
        --top;
        comp[++Count].pb(s);
    }while (x != s.u || y != s.v);

}

void DFS(int i)
{
    v[i] = 1;
 //   printf ("%d \n", i);
    lowpoint[i] = depth[i] = ++adancime;
    for (nod *p = G[i]; p; p = p->next)
        if (!v[p->x])
        {
            ++top;
            stack[top].u = i;
            stack[top].v = p->x;
            DFS(p->x);
            if (lowpoint[i] >= depth[i])
                update(i, p->x);
            lowpoint[i] = min(lowpoint[i], lowpoint[p->x]);
        }
        else
            lowpoint[i] = min(lowpoint[i], depth[p->x]);
}

int main()
{

    FILE *f = fopen("biconex.in", "r");
    fscanf(f, "%d%d", &n, &m);
    for (int x, y;m; --m)
    {
        fscanf(f, "%d%d", &x, &y);
        addMuchie(x, y);
        addMuchie(y, x);
    }
    fclose(f);
    for (int i = 1; i <= n; ++i)
        if (!v[i])
            adancime = 0, DFS(i);
//    afis();
    f = fopen("biconex.out", "w");
        fprintf (f, "%d ", Count);
    fclose(f);

    return 0;
}