Pagini recente » Cod sursa (job #2666807) | Cod sursa (job #3286323) | Cod sursa (job #1740078) | Cod sursa (job #99405) | Cod sursa (job #2667880)
#include<stdio.h>
#include<vector>
#include<string.h>
using namespace std;
#define NMAX 100005
#define INF 1000000000
vector<int> graph[NMAX], biconexe[NMAX], split_members[NMAX];
int high[NMAX], dfs_sons[NMAX], level[NMAX];
char viz[NMAX];
bool critic[NMAX];
int n, m, num_bic;
void dfs_critic(int node) {
//printf("Nod %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(critic[vecin]) {
split_members[vecin].push_back(node);
// printf("membru %d %d\n", vecin, node);
}
if(high[vecin] >= level[node]) {
critic[node] = true;
split_members[node].push_back(vecin);
//printf("membru %d %d\n", node, vecin);
}
high[node] = min(high[node], high[vecin]);
}
}
}
void dfs_biconexe(int node, int index_bic);
void split_biconexe(int node) {
//printf("Fac split in %d\n", node);
viz[node] = 1;
for(auto vecin : split_members[node]) {
if(viz[vecin]) {
continue;
}
if(critic[vecin]) {
//printf("Split din %d in %d\n", node, vecin);
split_biconexe(vecin);
}
//printf("Dfs din %d in %d\n", node, vecin);
biconexe[++num_bic].push_back(node);
dfs_biconexe(vecin, num_bic);
}
}
void dfs_biconexe(int node, int index_bic) {
//printf("M am dus in %d %d\n", node, index_bic);
viz[node] = 1;
biconexe[index_bic].push_back(node);
for(auto vecin : graph[node]) {
if(viz[vecin]) {
continue;
}
if(critic[vecin]) {
// printf("Split din %d in %d\n", node, vecin);
split_biconexe(vecin);
}
// printf("Dfs din %d in %d\n", node, vecin);
dfs_biconexe(vecin, index_bic);
}
}
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 = 1; i <= n; i++) {
if(critic[i]) {
split_biconexe(i);
break;
}
}
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;
}