Cod sursa(job #2667880)

Utilizator eudanipEugenie Daniel Posdarascu eudanip Data 4 noiembrie 2020 00:20:12
Problema Componente biconexe Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.06 kb
#include<stdio.h>
#include<vector>
#include<string.h>

using namespace std;

#define NMAX 100005
#define INF 1000000000

vector<int> graph[NMAX], biconexe[NMAX], split_members[NMAX];
int high[NMAX], dfs_sons[NMAX], level[NMAX];
char viz[NMAX];
bool critic[NMAX];
int n, m, num_bic;

void dfs_critic(int node) {
    //printf("Nod %d\n", node);
    viz[node] = 1;
    for(auto vecin : graph[node]) {
        if(viz[vecin]) {
            high[node] = min(high[node], level[vecin]);
        } 
        else {
            level[vecin] = level[node] + 1;
            dfs_sons[node]++;
            
            dfs_critic(vecin);
            if(critic[vecin]) {
                split_members[vecin].push_back(node);
               // printf("membru %d %d\n", vecin, node);
            }
            if(high[vecin] >= level[node]) {
                critic[node] = true;
                split_members[node].push_back(vecin);
                //printf("membru %d %d\n", node, vecin);
            }
            high[node] = min(high[node], high[vecin]);
        }
    }
}

void dfs_biconexe(int node, int index_bic);

void split_biconexe(int node) {
    //printf("Fac split in %d\n", node);
    viz[node] = 1;
    for(auto vecin : split_members[node]) {
        if(viz[vecin]) {
            continue;
        }
        
        if(critic[vecin]) {
            //printf("Split din %d in %d\n", node, vecin);
            split_biconexe(vecin);
        }
        //printf("Dfs din %d in %d\n", node, vecin);
        biconexe[++num_bic].push_back(node);
        dfs_biconexe(vecin, num_bic);
    }
}

void dfs_biconexe(int node, int index_bic) {
    //printf("M am dus in %d %d\n", node, index_bic);
    viz[node] = 1;
    biconexe[index_bic].push_back(node);
    for(auto vecin : graph[node]) {
        if(viz[vecin]) {
            continue;
        }
        if(critic[vecin]) {
        //    printf("Split din %d in %d\n", node, vecin);
            split_biconexe(vecin);
        }
      //  printf("Dfs din %d in %d\n", node, vecin);
        dfs_biconexe(vecin, index_bic);
    }
}

int main() {
    int a, b;
    
    freopen("biconex.in", "r", stdin);
    freopen("biconex.out", "w", stdout);
    
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= m; i++) {
        scanf("%d%d", &a, &b);
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    for(int i = 1; i <= n; i++) {
        high[i] = INF;
    }
    
    dfs_critic(1);
    critic[1] = (dfs_sons[1] > 1);
    
    /*printf("Nodurile critice sunt:\n");
    for(int i = 1; i <= n; i++) {
        if(critic[i]) {
            printf("%d ", i);
        }
    }
    printf("\n");*/
    
    memset(viz, 0, sizeof(viz));
    for(int i = 1; i <= n; i++) {
        if(critic[i]) {
            split_biconexe(i);
            break;
        }
    }
    
    printf("%d\n", num_bic);
    for(int i = 1; i <= num_bic; i++) {
        for(auto elem : biconexe[i]) {
            printf("%d ", elem);
        }
        printf("\n");
    }
    
    
    return 0;
}