Pagini recente » Cod sursa (job #2333919) | Cod sursa (job #878306) | Cod sursa (job #3030933) | Cod sursa (job #1236413) | Cod sursa (job #2098146)
#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;
}