Cod sursa(job #1643570)

Utilizator pusi23Faier Andreea pusi23 Data 9 martie 2016 19:21:40
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
#include<iostream>
#include<fstream>
using namespace std;
ifstream f("dfs.in");
ofstream g("dfs.out");
int viz[100003],n,m,u,v,i,nc;
struct nod
{
    int vecin;
    nod *adr;
};
nod *lv[100003], *p;
void dfs(int vf)
{
    nod *p;
    int y;
    viz[vf]=1;
    for(p=lv[vf];p!=0;p=p->adr)
    {
        y=p->vecin;
        if(viz[y]==0)
            dfs(y);
    }
}
int main()
{
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>u>>v;
        p=new nod;
        p->vecin=v;
        p->adr=lv[u];
        lv[u]=p;
        p=new nod;
        p->vecin=u;
        p->adr=lv[v];
        lv[v]=p;
    }
    for(i=1;i<=n;i++)
    {
        if(viz[i]==0)
        {
            nc++;
            dfs(i);
        }
    }
    g<<nc;
    f.close();
    g.close();
    return 0;
}