Pagini recente » Cod sursa (job #2977797) | Cod sursa (job #2424474) | Cod sursa (job #1125297) | Cod sursa (job #241188) | Cod sursa (job #3185441)
#include <stdio.h>
#include <stdlib.h>
enum Colour{White,Gray,Black};
typedef struct Node{
Colour colour;
int discovery_time,finish_time;
Node *parent;
int adjListSize;
Node **adjList;
};
typedef struct Graph{
int graph_size;
Node **vertices;
};
int time=0,numCC=0;
void DFS_VISIT(Node *current_node){
time+=1;
current_node->colour=Gray;
current_node->discovery_time=time;
for(int i=0;i<current_node->adjListSize;i++)
if(current_node->adjList[i]->colour==White) {
DFS_VISIT(current_node->adjList[i]);
}
current_node->colour=Black;
time+=1;
current_node->finish_time=time;
}
void DFS(Graph *graph){
for(int i=0;i<graph->graph_size;i++){
graph->vertices[i]->colour=White;
graph->vertices[i]->discovery_time=0;
graph->vertices[i]->finish_time=0;
graph->vertices[i]->parent=NULL;
}
time=0;
numCC=0;
for(int i=0;i<graph->graph_size;i++)
if(graph->vertices[i]->colour==White) {
DFS_VISIT(graph->vertices[i]);
numCC++;
}
}
void Undirected(){
Graph graph;
int n,m,x,y;
scanf("%d",&n);
scanf("%d",&m);
graph.graph_size=n;
graph.vertices=(Node **) malloc(sizeof(Node *)*n);
for(int i=0;i<graph.graph_size;i++) {
graph.vertices[i] = (Node *) malloc(sizeof(Node));
graph.vertices[i]->adjListSize=0;
graph.vertices[i]->adjList=(Node **) malloc(sizeof(Node *));
}
for(int i=0;i<m;i++){
scanf("%d",&x);
scanf("%d",&y);
graph.vertices[x-1]->adjList=(Node **) realloc(graph.vertices[x-1]->adjList, sizeof(Node *)*(graph.vertices[x-1]->adjListSize+1));
graph.vertices[y-1]->adjList=(Node **) realloc(graph.vertices[y-1]->adjList, sizeof(Node *)*(graph.vertices[y-1]->adjListSize+1));
graph.vertices[x-1]->adjList[graph.vertices[x-1]->adjListSize++]=graph.vertices[y-1];
graph.vertices[y-1]->adjList[graph.vertices[y-1]->adjListSize++]=graph.vertices[x-1];
}
// for(int i=0;i<n;i++)
// if(graph.vertices[i]->adjListSize<n){
// graph.vertices[i]->adjList=(Node **) realloc(graph.vertices[i]->adjList, sizeof(Node *)*graph.vertices[i]->adjListSize);
// }
DFS(&graph);
printf("%d",numCC);
}
int main() {
freopen("dfs.in","r",stdin);
freopen("dfs.out","w",stdout);
Undirected();
return 0;
}