Cod sursa(job #1227821)

Utilizator DanyPrvPirvoaica Daniel DanyPrv Data 11 septembrie 2014 21:18:07
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include <fstream>
#include <vector>
using namespace std;
ifstream f("dfs.in");
ofstream g("dfs.out");
vector <int> a[100001];
int nrel[200001],nrc,n,m,x,y,q[100001];
bool viz[200001];
void coada(int k);
int main()
{
    f>>n>>m;
    for(int i=1;i<=m;i++){
        f>>x>>y;
        a[x].push_back(y);
        a[y].push_back(x);
        ++nrel[x];
        ++nrel[y];
    }
    //add primul element
    for(int i=1;i<=n;i++){
        if(!viz[i]){
            ++nrc;
            coada(i);
        }

    }
    g<<nrc;
    return 0;
}




void coada(int k){
    int p=1,u=1;
    q[1]=k;
    viz[k]=1;
    while(p<=u){

//////////////////////////////
        for(int i=0;i<nrel[q[p]];i++){
            if(!viz[a[q[p]][i]]){
                viz[a[q[p]][i]]=1;
                q[++u]=a[q[p]][i];
            }
        }

        p++;
    }
}