Pagini recente » Cod sursa (job #636351) | Cod sursa (job #1563197) | Cod sursa (job #212301) | Cod sursa (job #868805) | Cod sursa (job #672406)
Cod sursa(job #672406)
#include <stdio.h>
#include <stdlib.h>
#include <queue>
struct node {
int value;
int weight;
struct node *next;
};
struct list {
node *head;
};
int dfs_time;
std::vector<int> order;
list* create_list()
{
list *l = (list*)calloc(1, sizeof(list));
l->head = NULL;
return l;
}
void insert_list(list* l, int value, int weight)
{
if (l->head == NULL) {
l->head = (node*)calloc(1, sizeof(node));
l->head->value = value;
return;
}
node *p = l->head;
while (p->next != NULL)
p = p->next;
node *n = (node*)calloc(1, sizeof(node));
n->value = value;
n->weight = weight;
p->next = n;
}
void destroy_list(list **l)
{
while ((*l)->head != NULL) {
node *p = (*l)->head;
(*l)->head = (*l)->head->next;
free(p);
}
}
enum colors {
WHITE = 0,
GRAY,
BLACK
};
struct graph {
int n;
list **adj;
int *colors;
int *parents;
};
graph* create_graph(int size)
{
graph *g = (graph*)calloc(1, sizeof(graph));
g->n = size;
g->adj = (list**)calloc(size, sizeof(list*));
g->colors = (int*)calloc(size, sizeof(int));
g->parents = (int*)calloc(size, sizeof(int));
return g;
}
void add_graph_edge(graph *g, int v1, int v2, int w)
{
if (g->adj[v1] == NULL)
g->adj[v1] = create_list();
insert_list(g->adj[v1], v2, w);
}
void clear_graph_value(graph *g)
{
for (int i = 0; i < g->n; i++) {
g->colors[i] = WHITE;
g->parents[i] = -1;
}
}
void destroy_graph(graph **g)
{
for (int i = 0; i < (*g)->n; i++) {
if ((*g)->adj[i])
destroy_list(&((*g)->adj[i]));
}
free((*g)->adj);
free((*g)->colors);
free((*g)->parents);
free(*g);
}
void bfs(graph *g, int s)
{
std::queue<int> nodes;
clear_graph_value(g);
g->colors[s] = GRAY;
g->parents[s] = -1;
nodes.push(s);
while (nodes.size()) {
int x = nodes.front();
printf("%d ", x);
node *n = NULL;
if (g->adj[x])
n = g->adj[x]->head;
while (n) {
if (g->colors[n->value] == WHITE) {
g->colors[n->value] = GRAY;
g->parents[n->value] = x;
nodes.push(n->value);
}
n = n->next;
}
nodes.pop();
g->colors[x] = BLACK;
}
printf("\n");
}
void print_graph_path(graph *g, int source, int dest)
{
int x = dest;
std::vector<int> path;
do {
path.push_back(x);
x = g->parents[x];
} while (x != -1);
printf("Path from %d to %d\n", source, dest);
for (std::vector<int>::reverse_iterator it = path.rbegin();
it != path.rend(); ++it) {
printf("%d ", *it);
}
printf("\n");
}
void dfs(graph *g, int x)
{
//g->start_time[node] = dfs_time;
//dfs_time++;
node *n = NULL;
if (g->adj[x])
n = g->adj[x]->head;
while (n) {
if (g->colors[n->value] == WHITE) {
g->colors[n->value] = GRAY;
g->parents[n->value] = x;
dfs(g, n->value);
}
n = n->next;
}
//g->end_time[node] = dfs_time;
dfs_time++;
order.push_back(x);
}
int main()
{
int v, e;
graph * g = NULL;
freopen("sortaret.in", "r", stdin);
freopen("sortaret.out", "w", stdout);
scanf("%d %d\n", &v, &e);
g = create_graph(v);
for (int i = 0; i < e; i++) {
int v1, v2, w;
scanf("%d %d\n", &v1, &v2);
add_graph_edge(g, v1 - 1, v2 - 1, 0);
}
int dfs_time = 0;
clear_graph_value(g);
for (int i = 0; i < g->n; i++) {
if (g->colors[i] == WHITE)
dfs(g, i);
}
for (std::vector<int>::reverse_iterator it = order.rbegin(); it != order.rend(); ++it)
printf("%d ", *it + 1);
printf("\n");
destroy_graph(&g);
return 0;
}