Mai intai trebuie sa te autentifici.

Cod sursa(job #2668336)

Utilizator madalin_frFrincu Madalin madalin_fr Data 4 noiembrie 2020 19:47:50
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.03 kb
#include <stdio.h>
#include <vector>
#include <string.h>
#define NMAX 100005
#define INF 1000000000
using namespace std;
int n,m;
vector<int> A[NMAX],tree[NMAX], biconexe[NMAX];
int high[NMAX], viz[NMAX], level[NMAX], father[NMAX];
bool critic[NMAX];
void dfs_critic(int node)
{
    viz[node] = 1;
    for(int vecin : A[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 "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(int vecin : tree[node])
    {
        if(!viz[vecin]) {
            dfs_biconexe(vecin, index_comp);
        }
    }
}

int main()
{
int num_bic = 0;
int a,b,i;
freopen("biconex.in","r",stdin);
freopen("biconex.out","w",stdout);
scanf("%d %d", &n, &m);
for(i=0;i<m;i++)
{
    scanf("%d %d", &a, &b);
    A[a].push_back(b);
    A[b].push_back(a);
}   
for(i=1;i<=n;i++)
{
    high[i]=INF;
}
dfs_critic(1);
memset(viz,0,sizeof(viz));
for(i=2;i<=n;i++)
{
    if(!viz[i]) {
        dfs_biconexe(i, ++num_bic);
    }
}
printf("%d\n", num_bic);
for(i=1;i<=num_bic;i++)
{
    for(int elem : biconexe[i])
    {
        printf("%d ", elem);
    }
    printf("\n");
}

return 0;
}