Cod sursa(job #1918536)

Utilizator eryk99Petrescu Eryk eryk99 Data 9 martie 2017 15:50:54
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 kb
#include <cstdio>
using namespace std;
int  n,m,viz[100005],cnt,x,i,y;
typedef struct nod
{
    int inf;
    nod *leg;
} *pNod;
pNod v[100005];

void add(pNod &dest, int val)
{
    pNod p;
    p=new nod;
    p->inf= val;
    p->leg= dest;
    dest= p;
}
void dfs(int nod)
{
    pNod p;
    viz[nod]=1;
    for (p=v[nod];p!=0;p=p->leg)
        if (viz[p->inf]==0) dfs(p->inf);
}
int main()
{
    freopen("dfs.in","r",stdin);
    freopen("dfs.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        add(v[x],y);
        add(v[y],x);
    }
    for (i=1;i<=n;i++)
        if (viz[i]==0) { cnt++; dfs(i);}
    printf("%d\n",cnt);
    return 0;
}