Mai intai trebuie sa te autentifici.
Cod sursa(job #2668336)
Utilizator | 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;
}