Cod sursa(job #3185415)

Utilizator razviOKPopan Razvan Calin razviOK Data 18 decembrie 2023 20:29:35
Problema Parcurgere DFS - componente conexe Scor 5
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.24 kb
#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]->colour=White;
        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,graph.vertices[x-1]->adjListSize);
        }

    DFS(&graph);
    printf("%d",numCC);
}
int main() {

    freopen("dfs.in","r",stdin);
    freopen("dfs.out","w",stdout);
    Undirected();

    return 0;
}