Pagini recente » Cod sursa (job #2598996) | Cod sursa (job #2918230) | Cod sursa (job #779553) | Cod sursa (job #2419041) | Cod sursa (job #3185434)
#include <stdio.h>
#include <stdlib.h>
enum Colour{White,Gray,Black};
typedef struct Node{
int key;
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]->colour=White;
graph.vertices[i]->key=i+1;
graph.vertices[i]->discovery_time=0;
graph.vertices[i]->finish_time=0;
graph.vertices[i]->parent=NULL;
graph.vertices[i]->adjListSize=0;
graph.vertices[i]->adjList=(Node **) malloc(sizeof(Node *)*n);
}
for(int i=0;i<m;i++){
scanf("%d",&x);
scanf("%d",&y);
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;
}