Cod sursa(job #833820)

Utilizator robertxxlRobert Luca robertxxl Data 13 decembrie 2012 09:10:16
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 kb
#include<fstream>
using namespace std;
ifstream f("dfs.in");
ofstream g("dfs.out");
int nr,viz[100001],k,n,m,x,y;
struct nod
{
    int inf;
    nod *adr;
}*l[100001];
void create(int i,int j)
{
    nod *c=new nod;
    c->inf=j;
    c->adr=l[i];
    l[i]=c;
}
void dfs(int a)
{
    nod *c=l[a];
    viz[a]=1;
    for(;c;c=c->adr)
        if(!viz[c->inf])
        {
            viz[c->inf]=1;
            dfs(c->inf);
        }
}
int main ()
{
    f>>n>>m;
    for(k=1;k<=m;++k)
    {
        f>>x>>y;
        create(x,y);
        create(y,x);
    }
    for(k=1;k<=n;++k)
    {
        if(!viz[k])
        {
            dfs(k);
            ++nr;
        }
    }
    g<<nr;
    return 0;
}