Cod sursa(job #2610574)

Utilizator DevilOnFieldTudor Horia Niculescu DevilOnField Data 5 mai 2020 02:38:29
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.71 kb
#include<stdio.h>
#include<vector>
#include<utility>

using namespace std;

const int MAXN = 100001;

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

FILE *in, *out;

void get_bcc(int x, int y) {
    vector<int> rez = vector<int> ();
    int tx, ty;
    do {
        tx = dfs_st.back().first;
        ty = dfs_st.back().second;
        dfs_st.pop_back();
        rez.push_back(ty);
    }
    while (tx != x || ty != y);
    rez.push_back(tx);
    sol.push_back(rez);
}

void tarj(int n) {
/*
    printf("pre %d: ", n);
    for(auto &it : dfs_st) {
        printf("%d %d | ", it.first, it.second);
    }
    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();
    for(auto &it : g[n]) {
        //printf("sunt in %d am vecinu %d\n\n", n, it);
        if(!viz[it]) {
            dfs_st.push_back(make_pair(n, it));
            dad[it] = n;
            tarj(it);
            //printf("in %d, it = %d returns x = %d\n", n, it, min_back[it]);

            if(min_back[it] == pozS[n]) {
                //printf("am gasit BCC din muchia %d %d\n", n, it);
                get_bcc(n, it);
            }
            min_back[n] = min(min_back[n], min_back[it]);
        } else {
            //printf("%d vecinu = %d: min_back[eu] = %d  pozS[vecin] = %d\n", n, it, min_back[n], pozS[it]);
            min_back[n] = min(min_back[n], pozS[it]);
        }
    }
/*
    printf("rec %d: ", n);
    for(auto &it : dfs_st) {
        printf("%d %d | ", it.first, it.second);
    }
    printf("\n");
*/

    if(dad[n] == 0 && g[n].size() == 0) {
        vector<int> rez = vector<int>();
        rez.push_back(n);
        sol.push_back(rez);
        dfs_st.pop_back();
    }
/*
    printf("fin %d: ", n);
    for(auto &it : dfs_st) {
        printf("%d %d | ", it.first, it.second);
    }
    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);
        }
    }

    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;
}