Pagini recente » Cod sursa (job #1463264) | Cod sursa (job #336292) | Cod sursa (job #336298) | Cod sursa (job #3272668) | Cod sursa (job #2667916)
#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;
}