Cod sursa(job #1028685)

Utilizator alexsuciuAlex Suciu alexsuciu Data 14 noiembrie 2013 15:57:50
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.66 kb
#include<iostream>
#include<fstream>
using namespace std;

int n,m,x,y,i,k,viz[100005];

struct nod
{
    int val;
    nod *next;
};
nod *p,*l[200002];


void dfs(int x)
{nod *p;
    viz[x]=1;
    for(p=l[x];p;p=p->next)
        if(!viz[p->val]) dfs(p->val);
}

int main()
{
    ifstream f("dfs.in");
    ofstream g("dfs.out");
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>x>>y;
        p=new nod;
        p->val=y;
        p->next=l[x];
        l[x]=p;
        p=new nod;
        p->val=x;
        p->next=l[y];
        l[y]=p;
    }
    for(i=1;i<=n;i++)
    {
        if(!viz[i]) {k++; dfs(i);}
    }
    g<<k;}