Cod sursa(job #896817)

Utilizator michael9ufoStanescu Mihai michael9ufo Data 27 februarie 2013 17:28:29
Problema Algoritmul lui Dijkstra Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.56 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

int N, M, i, j, rez=0;

vector<int> V[100005];


struct nod{
int inf;
nod *next;
};

nod *ha[100005];

void add(nod *&dest, int val)
{
    nod *p = new nod;
    p->inf = val;
    p->next = dest;
    dest = p;

}
int VIZ[100005];

void solve2(int now)
{

    VIZ[now] = 1;
   // for(vector<int>::iterator it=V[now].begin();it!=V[now].end();++it)
    //    if(!VIZ[*it])
       //     solve(*it);
       nod *p;
       /*
for(p=ha[now];p != NULL;p=p->next)
    if(!VIZ[p->inf])
        solve(p->inf);*/
}

void solve(int now)
{

    queue<int> Q;
    Q.push(now);

    while(!Q.empty())
    {
        int nod = Q.front();

        for(vector<int>::iterator it=V[nod].begin();it!=V[nod].end();++it)
            if(!VIZ[*it])
            {

                Q.push(*it);
                VIZ[*it] = 1;
            }

        Q.pop();

    }
}

int main()
{

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

    cin>>N>>M;

    for(i=1;i<=M;++i)
    {
        int A, B;
        scanf("%d %d", &A, &B);
        V[A].push_back(B);
        V[B].push_back(A);
      // add(ha[A], B);
       //add(ha[B], A);
    }

    for(i=1;i<=N;++i)
        if(!VIZ[i])
        {
            ++rez;
            solve(i);
        }
/*
for(i=1;i<=N;++i)
{


    for(nod *p=ha[i];p != NULL;p=p->next)
        cout<<p->inf<<" ";

 cout<<endl;
}
cout<<endl;*/
    cout<<rez<<"\n";

    return 0;
}