Cod sursa(job #1552999)

Utilizator andrei_diaconuAndrei Diaconu andrei_diaconu Data 19 decembrie 2015 00:22:55
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.8 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, 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);
}