Cod sursa(job #2667916)

Utilizator eudanipEugenie Daniel Posdarascu eudanip Data 4 noiembrie 2020 02:34:00
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.39 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], dfs_sons[NMAX], level[NMAX], father[NMAX];
char viz[NMAX];
bool critic[NMAX];
int n, m, num_bic;

void dfs_critic(int node) {
  //  printf("ma duc in %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(high[vecin] >= level[node]) {
                critic[node] = true;
                father[vecin] = node;
              //  printf("father de %d e %d\n", vecin, node);
            }
            else {
//                printf("muchie %d %d\n", vecin, node);
                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);
        }
    }
}

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