Cod sursa(job #330744)

Utilizator freak93Adrian Budau freak93 Data 11 iulie 2009 14:15:59
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include<fstream>
#define maxn 100005

using namespace std;

ifstream f("dfs.in");
ofstream g("dfs.out");

int n,m,i,j,x,y,passed[maxn],con;

struct nod
{
    nod *next;
    int v;
}
*a[maxn],*aux;

void go(int x)
{
    passed[x]=1;
    for(nod *i=a[x];i;i=i->next)
        if(passed[i->v]==0)
            go(i->v);
}

int main()
{
    f>>n>>m;
    for(i=1;i<=m;++i)
    {
        f>>x>>y;
        aux=new nod;
        aux->v=y;
        aux->next=a[x];
        a[x]=aux;
        aux=new nod;
        aux->v=x;
        aux->next=a[y];
        a[y]=aux;
    }

    for(i=1;i<=n;++i)
        if(!passed[i])
            ++con,go(i);

    g<<con<<"\n";

    f.close();
    g.close();

    return 0;
}