Cod sursa(job #1552959)

Utilizator andrei_diaconuAndrei Diaconu andrei_diaconu Data 18 decembrie 2015 23:30:29
Problema Componente biconexe Scor 46
Compilator cpp Status done
Runda Arhiva educationala Marime 1.72 kb
#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);
}