Cod sursa(job #1112979)

Utilizator mihaivasilacheMIhai Vasilache mihaivasilache Data 20 februarie 2014 10:56:13
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include <fstream>
using namespace std;
FILE*fin;
ofstream fout("dfs.out");
int a,b,n,m,comp,viz[100001];
struct element
{
    int v;
    element *adr;
}*l[100001],*q;
void dfs(int k)
{
    element *i;
    viz[k]=1;
    for(i=l[k];i!=NULL;i=i->adr)
        if(viz[i->v]!=1)
            dfs(i->v);
}
int main()
{
    int i;
    fin=fopen("dfs.in","r");
    fscanf(fin,"%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
        fscanf(fin,"%d%d",&a,&b);
        q=new element;
        q->v=b;
        q->adr=l[a];
        l[a]=q;
        q=new element;
        q->v=a;
        q->adr=l[b];
        l[b]=q;
    }
    for(i=1;i<=n;i++)
    {
        if(viz[i]!=1)
        {
            comp++;
            dfs(i);
        }
    }
    fout<<comp;
    return 0;
}