Pagini recente » Cod sursa (job #267063) | Cod sursa (job #3289727) | Cod sursa (job #336305) | Cod sursa (job #161971) | Cod sursa (job #2667917)
#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;
}