Pagini recente » Cod sursa (job #1898425) | Cod sursa (job #1386078) | Cod sursa (job #1420186) | Cod sursa (job #1328288) | Cod sursa (job #1552999)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define NMAX 100001
#define MIN(X,Y) (((X)>(Y))?(Y):(X))
typedef struct nod{
int idx;
struct nod* next;
}NOD;
int n, m, count, nbcc;
NOD* adj[NMAX];
NOD* stack;
int prenum[NMAX];
int low[NMAX];
NOD* bcc[NMAX];
//using namespace std;
NOD* add(NOD* cap, int u) {
NOD* p;
p = (NOD*)malloc(sizeof(NOD));
p->idx = u;
p->next = cap;
return p;
}
void readData() {
FILE* fin = fopen("biconex.in", "rt");
int i, u, v;
fscanf(fin, "%d %d", &n, &m);
for(i = 0; i < m; i++) {
fscanf(fin, "%d %d", &u, &v);
adj[u] = add(adj[u], v);
adj[v] = add(adj[v], u);
}
fclose(fin);
}
void dfs(int tata, int node) {
NOD* p, *q;
int v;
count++;
prenum[node] = count;
low[node] = count;
stack = add(stack, node);
p = adj[node];
while (p != NULL) {
v = p->idx;
if (v != tata)
if (prenum[v] == 0) {
dfs(node, v);
low[node] = MIN(low[node], low[v]);
if (low[v] >= prenum[node]) {
bcc[nbcc] = NULL;
bcc[nbcc] = add(bcc[nbcc], node);
//while (stack->idx != node) {
do{
bcc[nbcc] = add(bcc[nbcc], stack->idx);
q = stack;
stack = stack->next;
free(q);
}while(v != bcc[nbcc]->idx);
nbcc++;
}
}
else
low[node] = MIN(low[node], prenum[v]);
p = p->next;
}
}
int main() {
int i;
FILE* fout = fopen("biconex.out", "wt");
NOD* p;
memset(adj, sizeof(adj), 0);
memset(prenum, sizeof(prenum), 0);
memset(bcc, sizeof(bcc), 0);
readData();
count = 0; nbcc = 0; stack = NULL;
dfs(0, 1);
fprintf(fout, "%d\n", nbcc);
for (i = 0; i < nbcc; i++) {
p = bcc[i];
while (p != NULL) {
fprintf(fout, "%d ", p->idx);
p = p->next;
}
fprintf(fout, "\n");
}
fclose(fout);
}