Cod sursa(job #735241)

Utilizator visanrVisan Radu visanr Data 15 aprilie 2012 21:53:25
Problema Parcurgere DFS - componente conexe Scor 85
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include <cstdio>
#include <cstdlib>
#include <vector>
using namespace std;

#define nmax 100000

struct edge
{
       vector<long> neighbour;
};
edge nodes[nmax];
int used[nmax];
long n,m,x,y;


void read_input()
{
     scanf("%ld %ld", &n,&m);
     for(int i=0;i<m;i++)
     {
             scanf("%ld %ld", &x,&y);
             nodes[x].neighbour.push_back(y);
             nodes[y].neighbour.push_back(x);
     }
}

void DFS(long node)
{
     used[node]=1;
     for(int i=0;i<nodes[node].neighbour.size();i++)
     {
             if(used[nodes[node].neighbour[i]]==0)
             {
                                                  DFS(nodes[node].neighbour[i]);
             }
     }
}

int main()
{
    freopen("dfs.in","r",stdin);
    freopen("dfs.out","w",stdout);
    long Counter=0;
    read_input();
    for(int i=1;i<=n;i++) if(used[i]==0) { Counter++; DFS(i);}
    printf("%ld\n", Counter);
    return 0;
}