Cod sursa(job #1131748)

Utilizator jul123Iulia Duta jul123 Data 1 martie 2014 12:41:18
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.58 kb
#include<iostream>
#include<cstdio>
#include<vector>
#include<stack>
#define MAX_N 100000

using namespace std;

int niv1[MAX_N], niv2[MAX_N], k=0, nr=0;
vector<int> a[MAX_N], cbc[MAX_N];
stack<pair<int, int> > st;

void dfs(int nod, int tata, int nivel)
{
   niv1[nod]=nivel;
   niv2[nod]=nivel;
   int i, u, x, y;
   for(i=0; i<a[nod].size(); i++) {
        u=a[nod][i];
        if(tata==u) continue;
        if(niv1[u]==-1) {
            st.push(make_pair(nod, u));
            dfs(u, nod, nivel+1);
            niv2[nod]=min(niv2[nod], niv2[u]);
            if(niv1[nod]<=niv2[u]) {
                do {
                        x=st.top().first;
                        y=st.top().second;
                        st.pop();
                        cbc[nr].push_back(y+1);
                } while(x!=nod && y!=u);
                cbc[nr].push_back(x+1);
                nr++;
            }
        }
        else
            niv2[nod]=min(niv2[nod], niv1[u]);
   }
}
int main()
{
    FILE *fin, *fout;
    fin=fopen("biconex.in", "r");
    fout=fopen("biconex.out", "w");

    int i, x, y, m, n, j;
    fscanf(fin, "%d %d", &n, &m);
    for(i=0; i<m; i++) {
        fscanf(fin, "%d %d", &x, &y);
        a[x-1].push_back(y-1);
        a[y-1].push_back(x-1);
    }
    for(i=0; i<n; i++) {
        niv1[i]=-1;
    }
    for(i=0; i<n; i++) {
        dfs(i, 0, 0);
    }
    fprintf(fout, "%d\n", nr);
    for(i=0; i<nr; i++) {
        for(j=0; j<cbc[i].size(); j++)
            fprintf(fout, "%d ", cbc[i][j]);
    fprintf(fout, "\n");
    }

}