Cod sursa(job #2667917)

Utilizator eudanipEugenie Daniel Posdarascu eudanip Data 4 noiembrie 2020 02:40:07
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.38 kb
#include<stdio.h>
#include<vector>
#include<string.h>

using namespace std;

#define NMAX 100005
#define INF 1000000000

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

void dfs_critic(int 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_critic(vecin);
            
            if(high[vecin] >= level[node]) {
                critic[node] = true;
                father[vecin] = node; 
                //Daca nodul este critic deoarece desparte componenta de ramura vecinului, despart componenta de vecin in tree dar marchez "node" ca sa fie bagat in componenta
            }
            else {
                tree[node].push_back(vecin);
                tree[vecin].push_back(node);
            }
            high[node] = min(high[node], high[vecin]);
        }
    }
}

void dfs_biconexe(int node, int index_comp) {
    viz[node] = 1;
    biconexe[index_comp].push_back(node);
    if(father[node]) {
        biconexe[index_comp].push_back(father[node]);
    }
    
    for(auto vecin : tree[node]) {
        if(!viz[vecin]) {
            dfs_biconexe(vecin, index_comp);
        }
    }
}
// construiesc componenta biconexa formata din nodurile conexe din tree + toate nodurile din father (nodurile critice care au despartit componenta de restul)

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);
    // fiecare componenta biconexa este un arbore partial al arborelui dfs
    
    memset(viz, 0, sizeof(viz));
    for(int i = 2; i <= n; i++) {
        if(!viz[i]) {
            dfs_biconexe(i, ++num_bic);
        }
    }
    
    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;
}