Cod sursa(job #2098179)

Utilizator adireusadireus adireus Data 2 ianuarie 2018 15:20:20
Problema Componente tare conexe Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 1.99 kb
#include <stdlib.h>
#include <stdio.h>
#include <string.h>


struct node
{
	void* data;
	struct node *next;
};

int list_add_front(struct node **head, void* val)
{
	struct node *tmp;
	tmp = malloc(sizeof(struct node));
	tmp->data = val;
	tmp->next = *head;

	*head = tmp;
	return 0;
}

int dfs(struct node **graph, int root, int *marked, int conr, int *order, int* oidx, struct node** out)
{
        if (out)
		list_add_front(out, (void *)root);
	marked[root] = conr;
	for(struct node* p = graph[root]; p != NULL; p = p->next)
		if(!marked[(int)p->data])
			dfs(graph, (int)p->data, marked, conr, order, oidx, out);

	if (order != NULL)
		order[(*oidx)++] = root;

	return 0;
}

int main()
{
	FILE *infile, *outfile;
	int n, m, i;
	int *order, *marked;
	struct node **grapht, **graph;	
	int count = 0, oidx = 0;
	struct node *output = NULL;
	struct node *temp = NULL;
	
		
	infile = fopen("ctc.in", "r");
	outfile = fopen("ctc.out", "w");
	
	fscanf(infile, "%d %d", &n, &m);
	marked = malloc((n+1) * sizeof(int));
	order = malloc((n+1) * sizeof(int));
	graph = malloc((n+1) * sizeof(struct node*));
	grapht = malloc((n+1) * sizeof(struct node*));

	memset(marked, 0, (n+1) * sizeof(int));
	for (i = 0; i <= n; i++) {
		graph[i] = NULL;
		grapht[i] = NULL;
	}
	
	for (i = 0; i < m; i++) {
		int u, v;
		fscanf(infile, "%d %d", &u, &v);
		// add reverse
		list_add_front(&grapht[v], (void *)u);
		list_add_front(&graph[u],  (void *)v);
	}
	
	for (i = 1; i <=n; i++)
		if (!marked[i]) 
			dfs(grapht, i, marked, 1, order, &oidx, NULL);
	
	
	memset(marked, 0, (n+1) * sizeof(int));
	
	for(i = oidx - 1; i >= 0; i--) {
		if(marked[order[i]])
			continue;
		count++;
		temp = NULL;
		dfs(graph, order[i], marked, count, NULL, NULL, &temp);
		list_add_front(&output, temp);
	}
	
	fprintf(outfile, "%d\n", count);
	
	for(struct node* p = output; p != NULL; p = p->next) {
		for(struct node* q = p->data; q != NULL; q = q->next)
			fprintf(outfile, "%d ", (int)q->data);
		fprintf(outfile, "\n");
	}
	fclose(infile);
	fclose(outfile);
	return 0;
}