Cod sursa(job #153133)

Utilizator savimSerban Andrei Stan savim Data 10 martie 2008 10:27:49
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.71 kb
#include <stdio.h>
#include <vector>
#define maxn 100010
using namespace std;
vector <int> a[maxn];
int n,m,i,j,k,p,q;
int fol[maxn];
void dfs(int k)
{
    int t=a[k].size(),i;
    
    for (i=0; i<=t-1; i++)
        if (fol[a[k][i]]==0)
        {
            fol[a[k][i]]=1;
            dfs(a[k][i]);
        }
}
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",&p,&q);
        a[p].push_back(q);
        a[q].push_back(p);
    }
    k=0;
    for (i=1; i<=n; i++)
    if (fol[i]==0)
    {
        k++;fol[i]=1;
        dfs(i);
    }

    printf("%d\n",k);


    return 0;
}