Cod sursa(job #1684327)

Utilizator morris18cmDumnezeu morris18cm Data 10 aprilie 2016 22:55:04
Problema Parcurgere DFS - componente conexe Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include <iostream>
#include <fstream>

using namespace std;

ifstream f("dfs.in");
ofstream d("dfs.out");

struct node
{
    int info;
    node *next;
}*graph[100000]={NULL};
int b[100000]={0};

void add_node(node* &b, int info);
void DFS(int i);

int main()
{
    int n,m,i,x,y;
    f>>n;
    f>>m;
    for(i=1;i<=m;i++)
    {
        f>>x;
        f>>y;
        add_node(graph[x],y);
        add_node(graph[y],x);
    }
    x=0;
    for(i=1;i<=n;i++)
        if(!b[i])
        {
            x++;
            DFS(i);
        }
    d<<x;
    return 0;
}

void add_node(node* &b, int info)
{
    node *q;
    q=new node;
    q->info=info;
    q->next=b;
    b=q;
}

void DFS(int i)
{
    node *q;
    b[i]=1;
    //cout<<i;
    for(q=graph[i];q!=NULL;q=q->next)
        if(!b[q->info])
            DFS(q->info);
}