Cod sursa(job #2005645)

Utilizator valorosu_300Cristian Gherman valorosu_300 Data 27 iulie 2017 18:16:12
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include <fstream>
using namespace std;
ifstream in("dfs.in");
ofstream out("dfs.out");
const int N = 100005;
struct nod{
    int nr;
    nod *urm;
}*v[N];
int st[N];
bool ver[N];
void adaug(int x, int y){
    nod *p = new nod;
    nod *q = new nod;
    p->nr = y;
    p->urm = v[x];
    v[x] = p;
    q->nr = x;
    q->urm = v[y];
    v[y] = q;
}
int dfs(int n, int ns){
    int l = 0, val, vf;
    bool g;
    st[++l] = ns;
    ver[ns] = true;
    while(l > 0){
        g = 0;
        vf = st[l];
        for(nod *nou = v[vf];nou && g == 0;nou = nou->urm){
            val = nou->nr;
            if(ver[val] == false){
                ver[val] = true;
                st[++l] = vf = val;
                g = 1;
            }
        }
        if(g == 0)
            vf = st[--l];
    }
}
int main()
{
    int n,m,x,y,cnt = 0;
    in>>n>>m;
    for(int i=1;i<=m;i++){
        in>>x>>y;
        adaug(x,y);
    }
    in.close();
    for(int i=1;i<=n;i++)
        if(ver[i] == false){
            cnt++;
            dfs(n,i);
        }
    out<<cnt<<"\n";
    out.close();
    return 0;
}