Cod sursa(job #1060162)

Utilizator DaNutZ2UuUUBB Bora Dan DaNutZ2UuU Data 17 decembrie 2013 18:17:11
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.89 kb
#include <stdio.h>
#include <vector>
#include <algorithm>
#define DIM 100010

using namespace std;

struct muchie {
    int a;
    int b;
};

struct nod {
    int inf;
    nod *adr;
};

nod *V[DIM], *q;

vector<int> L[DIM];
int N, M, X, Y, i, j, comp, s;
muchie r;

int Uz[DIM], Niv[DIM];

muchie S[2*DIM];

int minim (int a, int b) {
    return a<b ? a : b;
}

void dfs(int x, int t, int niv, int &nivMin) {
    Niv[x] = nivMin = niv;
    Uz[x] = 1;
    nod *q;
    for (q = V[x];q!=NULL;q = q->adr) {
        if (q->inf == t)
            continue;
        if (Uz[q->inf] == 0) {
            S[++s].a = x;
            S[s].b = q->inf;
            int nivMinFiu;
            dfs(q->inf, x, niv+1, nivMinFiu);
            nivMin = minim(nivMin, nivMinFiu);

            if (nivMinFiu >= niv) {
                ++comp;
                do {
                    r = S[s--];
                    L[comp].push_back(r.a);
                    L[comp].push_back(r.b);
                } while (!( r.a == x && r.b == q->inf  ));
            }

        } else {
            nivMin = minim(nivMin, Niv[q->inf]);
        }
    }
    Niv[x] = nivMin;
}


int main() {
    FILE *f = fopen("biconex.in","r");
    FILE *g = fopen("biconex.out","w");
    fscanf(f,"%d %d",&N, &M);
    for (i=1;i<=M;i++) {
        fscanf(f,"%d %d",&X, &Y);
        q = new nod;
        q->inf = Y;
        q->adr = V[X];
        V[X] = q;
        q = new nod;
        q->inf = X;
        q->adr = V[Y];
        V[Y] = q;
    }
    fclose(f);
    int nivMinFiu;
    dfs(1, 1, 1, nivMinFiu);
    fprintf(g,"%d\n",comp);
    for (i=1;i<=comp;i++) {
        L[i].push_back(DIM+1);
        sort(L[i].begin(), L[i].end());
        for (j=0;j<L[i].size()-1;j++)
            if (L[i][j] != L[i][j+1])
                fprintf(g,"%d ",L[i][j]);

        fprintf(g,"\n");
    }
    return 0;
}