Cod sursa(job #769258)

Utilizator igsifvevc avb igsi Data 18 iulie 2012 19:52:39
Problema Componente biconexe Scor 70
Compilator c Status done
Runda Arhiva educationala Marime 2.06 kb
#include<stdio.h>
#include<stdlib.h>
#define SIZE 100001

struct list{ int v; struct list *next;};
typedef struct list list;

FILE *in, *out;
int root[SIZE], level[SIZE], reach[SIZE], stack[SIZE][2], top, N, nrComponents;
char used[SIZE];
list *G[SIZE], *result[SIZE];

void DF(int node)
{
	list *p;
	int swX, swY;
	used[node] = 1;
	reach[node] = level[node];
	
	for(p = G[node]; p; p = p->next)
	{
		if(p->v != root[node] && level[p->v] < level[node])
			stack[++top][0] = node,
			stack[top][1] = p->v;
			
		if(!used[p->v])
		{
			level[p->v] = level[node] + 1;
			DF(p->v);
			
			if(reach[p->v] < reach[node])
				reach[node] = reach[p->v];
				
			else if(reach[p->v] >= level[node])
			{
				list *aux;
				nrComponents++;
				
				do
				{
					for(swX = swY = 1, aux = result[nrComponents]; aux && (swX || swY); aux = aux->next)
					{
						if(stack[top][0] == aux->v)
							swX = 0;
						if(stack[top][1] == aux->v)
							swY = 0;
					}
					if(swX)
					{
						aux = malloc(sizeof(list));
						aux->v = stack[top][0];
						aux->next = result[nrComponents];
						result[nrComponents] = aux;
					}					
					if(swY)
					{
						aux = malloc(sizeof(list));
						aux->v = stack[top][1];
						aux->next = result[nrComponents];
						result[nrComponents] = aux;
					}					
					top--;
				} while(stack[top+1][0] != node || stack[top+1][1] != p->v);
			}
		}
		else
			if(p->v != root[node] && reach[node] > level[p->v])
				reach[node] = level[p->v];
	}
}

int main()
{
	int M, a, b, i;
	list *p;
	
	in = fopen("biconex.in", "r");
	out = fopen("biconex.out", "w");
	
	fscanf(in, "%d %d", &N, &M);
	for(; M; --M)
	{
		fscanf(in, "%d %d", &a, &b);
		p = malloc(sizeof(list));
		p->v = b;
		p->next = G[a];
		G[a] = p;
		
		p = malloc(sizeof(list));
		p->v = a;
		p->next = G[b];
		G[b] = p;
	}
	
	for(i = 1; i <= N; ++i)
		if(!used[i])
		{
			level[i] = 1;
			DF(i);
			
		}
	
	fprintf(out, "%d\n", nrComponents);
	for(i = 1; i <= nrComponents; ++i)
	{
		for(p = result[i]; p; p = p->next)
			fprintf(out, "%d ", p->v);
		fprintf(out, "\n");
	}
	
	fclose(in);
	fclose(out);
	return 0;
}