Cod sursa(job #2098146)

Utilizator adireusadireus adireus Data 2 ianuarie 2018 14:31:39
Problema Componente tare conexe Scor 60
Compilator c Status done
Runda Arhiva educationala Marime 1.81 kb
#include <stdlib.h>
#include <stdio.h>

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

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

	*head = tmp;
	return 0;
}


int list_pop_front(struct node **head, int *val)
{
	struct node *tmp;
	*val = (*head)->data;

	tmp = *head;
	*head = (*head)->next;

	free(tmp);
	return 0;
}

int dfs(struct node **graph, int root, int *marked, int conr, struct node **list)
{
	if (marked[root])
		return 0;

	marked[root] = conr;
	for(struct node* p = graph[root]; p != NULL; p = p->next)
		dfs(graph, p->data, marked, conr, list);

	if (list != NULL)
		list_add_front(list, root);
	return 0;
}

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

	for (i = 0; i <= n; i++) {
		marked[i] = 0;
		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], u);
		list_add_front(&graph[u], v);
	}
	
	for (i = 1; i <=n; i++) 
		dfs(grapht, i, marked, 1, &order);
	
	
	for (i = 1; i <=n; i++)
		marked[i] = 0;

	while(order != NULL) {
		int curr;
		list_pop_front(&order, &curr);
		if(marked[curr])
			continue;
		count++;
		dfs(graph, curr, marked, count, NULL);
	}
	
	fprintf(outfile, "%d\n", count);
	for (i = 1; i <= count; i++) {
		for (int j = 1; j <=n; j++)
			if(marked[j] == i)
				fprintf(outfile, "%d ", j);
		fprintf(outfile, "\n");
	}

	fclose(infile);
	fclose(outfile);
	return 0;
}