Pagini recente » Cod sursa (job #232328) | Cod sursa (job #810468) | Cod sursa (job #51446) | Monitorul de evaluare | Cod sursa (job #1552959)
#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, nbic;
NOD* adj[NMAX];
NOD* stack;
int prenum[NMAX];
int low[NMAX];
NOD* bc[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]) {
bc[nbic] = NULL;
bc[nbic] = add(bc[nbic], node);
while (stack->idx != node) {
bc[nbic] = add(bc[nbic], stack->idx);
q = stack;
stack = stack->next;
free(q);
}
nbic++;
}
}
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);
readData();
count = 0; nbic = 0; stack = NULL;
dfs(0, 1);
fprintf(fout, "%d\n", nbic);
for (i = 0; i < nbic; i++) {
p = bc[i];
while (p != NULL) {
fprintf(fout, "%d ", p->idx);
p = p->next;
}
fprintf(fout, "\n");
}
fclose(fout);
}