Cod sursa(job #2098156)

Utilizator adireusadireus adireus Data 2 ianuarie 2018 14:41:58
Problema Componente tare conexe Scor 60
Compilator c Status done
Runda Arhiva educationala Marime 1.85 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, int *order, int* oidx)
{
	if (marked[root])
		return 0;

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

	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;
	
	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*));

	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, &oidx);
	
	
	for (i = 1; i <=n; i++)
		marked[i] = 0;

	for(i = oidx - 1; i >= 0; i--) {
		if(marked[order[i]])
			continue;
		count++;
		dfs(graph, order[i], marked, count, NULL, 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;
}