Cod sursa(job #2610568)

Utilizator DevilOnFieldTudor Horia Niculescu DevilOnField Data 5 mai 2020 01:24:27
Problema Componente biconexe Scor 46
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.54 kb
#include<stdio.h>
#include<vector>

using namespace std;

const int MAXN = 100001;

vector <int> g[MAXN], dfs_st;
bool viz[MAXN];
bool onS[MAXN];
int pozS[MAXN];
int dad[MAXN];
int min_back[MAXN];
vector <vector <int>> sol;

FILE *in, *out;

void get_bcc(int v) {
    vector<int> rez = vector<int> ();
    while(dfs_st.back() != v) {
        rez.push_back(dfs_st.back());
        onS[dfs_st.back()] = false;
        dfs_st.pop_back();
    }

    rez.push_back(v);
    sol.push_back(rez);
}

void tarj(int n, int d) {
/*
    printf("pre %d: ", n);
    for(auto &it : dfs_st) {
        printf("%d ", it);
    }
    printf("\n");
*/
    //printf("eu %d, sunt la %d pe sitva\n", n, dfs_st.size());


    viz[n] = true;
    min_back[n] = dfs_st.size();
    pozS[n] = dfs_st.size();
    dfs_st.push_back(n);
    onS[n] = true;
    for(auto &it : g[n]) {
        if(!viz[it]) {
            dad[it] = n;
            tarj(it, d + 1);
            //printf("in %d, it = %d returns x = %d\n", n, it, min_back[it]);

            if(min_back[it] == pozS[n]) {
                get_bcc(n);
            }
            min_back[n] = min(min_back[n], min_back[it]);
        } else {
            if(onS[it]) {
                if(dad[n] != 0) {
                    if(it != dad[n]) {
                        min_back[n] = min(min_back[n], pozS[it]);
                    }
                }
            }
        }
    }
/*
    printf("rec %d: ", n);
    for(auto &it : dfs_st) {
        printf("%d ", it);
    }
    printf("\n");
*/
    if(min_back[n] == pozS[n]) {
        min_back[n] = pozS[dad[n]];
    }

    if(dad[n] == 0 && g[n].size() == 0) {
        get_bcc(n);
    }
/*
    printf("fin %d: ", n);
    for(auto &it : dfs_st) {
        printf("%d ", it);
    }
    printf("\n");
*/
}




int main () {
    in = fopen("biconex.in", "r");
    out = fopen("biconex.out", "w");

    int n, m;
    fscanf(in, "%d %d", &n, &m);

    for(int i = 0; i < m; i++) {
        int x, y;
        fscanf(in, "%d %d", &x, &y);
        g[x].push_back(y);
        g[y].push_back(x);
    }

    fclose(in);

    for(int i = 1; i <= n; i++) {
        if(!viz[i]) {
            dad[i] = 0;
            tarj(i, 0);
            dfs_st.pop_back();
            onS[i] = false;
        }
    }

    fprintf(out, "%d\n", sol.size());
    for(auto &bcc : sol) {
        for(auto &elem : bcc) {
            fprintf(out, "%d ", elem);
        }
        fprintf(out, "\n");
    }

    fclose(out);

    return 0;
}